Best Index HackerEarth Problem
Task :- To calculate maximum special sum possible. Special sum for an index is given by taking the sum of groups of 1 element, then next 2 elements(if possible), then next 3 elements(if possible), then next 4 elements(if possible) and so on.
For eg: if arr=[ 2, 4, 5, 6, 7, -10 ]
For index 0: Special sum = (2) + (4+5) + (6+7–10) = 14
For index 1: Special sum = (4) + (5 +6) = 15
Note that we cannot take anymore elements as we have to take 3 elements for next group but only 2 elements are available
For index 2: Special sum = (5) + (6+7) = 18
For index 3: Special sum = (6) + (7–10) = 3
For index 4: Special sum = (7) = 7
For index 5: Special sum = (-10) = -10
The answer would be 18 as it is the maximum special sum possible.
Brute Force approach :- We can simply use two loops.The outer loop will specify the the starting index and the inner loop can calculate sum of possible group by iterating through the array(we can check if we can take the next group or not by calculating the number of remaining elements inside inner loop). This approach has a time complexity of O(N²) and results in Time Limit Exceed(TLE).
Brute Force Code :-
Efficient Logic :- We can use an array to store the cumulative sum of each index. We will use this array to calculate the sum of the required range directly(in constant time). Now we can keep track of group size possible and calculate the sum of that range, then if we do not have enough elements we have to get the next valid(decreased) group size.
The possible group sizes are 1,3,6,10,15, ……..
This is obtained by summing first n natural numbers.
1 -> 1
3 -> 1+2
6 -> 1+2+3 and so on
Group size = n*(n+1) /2
But we have to get group size from the number of elements remaining/available after an index.
Considering the above example: If we are at 1st index and the length of array(n) is 6 ,the no of remaining elements is obtained by n-1 = 6–1 = 5.
But 5 is not a valid group size, the next possible group size(<5) is 3.
So we need to get the next valid group size from the remaining elements.We can get this using the formula for first n natural numbers.
After rearranging terms in the formula we get :
n² + n — 2*(group_size) = 0 — — — — Quadratic eqn
In this if group_size is not valid i.e it doesn’t belong in {1,3,6,10,..} then the factor of this quadratic equation would be fractional and we can get the next valid group size by taking the floor value of this factor and calculating it using same equation (n*(n+1))/2.
For the above example: remaining elements = 5
So the equation becomes n² + n — 2*5 =0
n² + n -10 =0
Comparing above equation with a*n² + b*n + c =0
We get: a=1,b=1,c= -10 or (-2*remaining_elements)
By calculating factors will be:
(-b + SQRT(b² — 4*a*c) ) / 2 ,(-b — SQRT(b² — 4*a*c) ) / 2
We can ignore the second value as it would result in negative value which is not valid as n should be positive.
n comes close to 2.7 . So we take its floor value i.e- 2
Then valid group size= (n*(n+1))/2 = (2*3)/2 = 3 which is the correct valid group size possible.
We can create a function which takes the number of remaining elements as a parameter and returns a valid group size .
Note :- If no of the remaining elements is a valid group size we get the same answer in return.
— — — — — — — — — — — — — — — — — — — — — — — — — —
Explanation for cumulative sum array:
Let’s consider an array
A = [1, 5, 7, 2, 3, 8]
The cumulative sum array for this index looks like :
xsum= [0, 1, 6, 13, 15, 18, 26]
Now to get the sum of a subarray from L to R.
We can directly calculate it as ( xsum[R+1] — xsum[L] ) in constant time.
— — — — — — — — — — — — — — — — — — — — — — — — — —
Efficient Code :-
