# How to solve this?

Can anyone tell me a nice approach with a example to solve this problem

In this problem, we basically need to find N, such that S = 1^2 + 2^2 + 3^2 … N^N such that S <= Given Value and N is maximized.

Now, above summation can also be written as S = N*(N+1)(2N+1)/6.

So we need maximum value of N such that N*(N+1)(2N+1)/6 <= Given volume.

Now, we can do a simple binary search and get the answer in O(logN) time.

For binary Search, you may take left bound as 0 and right bound as 1e6. (because above expression is cubic and for values of N > 1e6, expression may overflow long range.)

I’ll post the solution soon.

A simple mathematical solution also exist, using above expression, but i won’t tell you. Enjoy.

1 Like

Another solution exist using reordering queries if you are not fond of binary search.

Give problems a try before rushing to solutions. Solution using binary search.

Solution using reordering of queries.

1 Like

No problem mate. 1 Like

Anyways, Here’s binary search function. (Take l = 0, r = 1e6)

``````static long ans(long value, long l, long r){
long mid = (l+r)/2;
long sum = (mid*(mid+1)*(2*mid+1))/6, sum2 = ((mid+2)*(mid+1)*(2*mid+3))/6;
if(value >= sum && value < sum2)return mid;
if(value >= sum2)return ans(value, mid+1, r);
return ans(value,l,mid-1);
}``````
1 Like

thanks a lot