# HBDY - Editorial

Practice

Contest Code Battle 2021.1.2

Author: Rahul Sharma

Tester: Naman Mittal, Akshit Monga

Editorialist: Arjun Kathail

Easy

# PREREQUISITES:

Basic math, binary search

# PROBLEM:

Given amount of cash X, Mukesh can select N sweets such that when arranged in single line cost of i^{th} sweet fromm left is i^{2}. Find the maximum sweets he can purchase. Total amount sweets available is 10^6.

# QUICK EXPLANATION:

The cost of N sweets will be N*(N+1)*(2N+1)/6. Do binary search from 1 to 10^6 and compare the cost with amount X. N for which total cost is closest to X on lower side is the answer.

# EXPLANATION:

Simple linear approach (Brute force).
Maintain a variable cost initialised to 0
Iterate from 1 to L where L is 10^6. At any i^{th} iteration update the cost as cost = cost + i^2. If cost > X then return i-1. This will be the answer but it is a brute force solution and only this sub-task will pass. Time Complexity: O(L).

An optimised approach will be to use binary search approach.
The cost of N sweets will be amount(N) =\sum_{i=1}^Ni^2=N*(N+1)*(2N+1)/6.
low= 1 and high = 10^6.
mid = (start + end)/2
If amount(mid) \leq X then res = mid and low = mid + 1 else high = mid - 1 and repeat till . Final answer will be in res i.e. maximum sweets he can buy. This approch will pass all sub-tasks.

# COMPLEXITIES:

Time Complexity: For best approach O(log L) where maximum limit of L is 10^6 per test case.
Auxillary Space Complexity: O(1) per test case.

# SOLUTIONS:

Language: C++, Python

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

long long int amount(long long int n)
{
long long int cost = n*(n+1)*(2*n+1);
return cost/6;
}

long long int maxSweets(long long int x)
{
long long int low = 1, high = 1000000, res = 0;
while (low <= high)
{
long long int mid = (low + high) / 2;

if (amount(mid)<=x) {
// Update res
res = mid;
// Update low
low = mid + 1;
}
else
// Update high
high = mid - 1;
}
return res;
}

int main()
{
long long int t, x;
cin >> t;
while(t--)
{
cin >> x;
cout << maxSweets(x) << '\n';
}
}

Tester's Solution
'''Author- Akshit Monga'''
import sys
def f(x):
return (x*(x+1)*(2*x+1))//6
t=int(input())
assert 1<=t<=10**4
for _ in range(t):
x=int(input())
assert 1<=x<=10**18
l=1
h=1000000
while 1:
mid=(l+h)//2
if h-l+1==1:
ans=l
break
if h-l+1==2:
if f(h)<=x:
ans=h
else:
ans=l
break
if f(mid)==x:
ans=mid
break
if f(mid)>x:
h=mid
else:
l=mid
print(ans)

2 Likes