HBDY - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest Code Battle 2021.1.2

Author: Rahul Sharma

Tester: Naman Mittal, Akshit Monga

Editorialist: Arjun Kathail

DIFFICULTY:

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:

Sub-task 1
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).

Sub-task 2
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