Find maximum value of Indices of Array that satisfy the given conditions

Given an integer N (N ≥ 5) Then assume you have two infinite arrays X and Y where X[] is an array of element N and each element of Y[] is 2ⁱ where i is the index of the array, the task is to find two indices let’s say A and B which are the maximum value of the index at which the prefix sum in X[] is at least the same as the prefix sum of Y[] and the index value at which the X[i] – Y[i] is maximum respectively, Where The value of B should be less than or equal to A. Formally, B ≤ A.

Examples:

Input: N = 7
Output: A = 5, B = 3
Explanation: Y[] = {1, 2, 4, 8….., 2i – n}, X[] = {7, 7, 7, 7, …..7}
The sum of X[] till index 5 is: 35 
The sum of Y[] till index 5 is: 31
5 is the maximum value of index at which, The sum of elements of X[] is strictly greater than or equal to Y[]. Maximum possible difference of sum(Xi – Yi) is at index 3, Which is 14. Therefore, A = 5 and B = 3.

Input: N = 6
Output: A = 4, B = 3
Explanation: It can be verified that 4 is maximum possible value of index at which sum of elements of X[] is strictly greater than or equal to Y[] and max difference is at index 3. Therefore, A = 4 and B = 3.

Approach: Implement the idea below to solve the problem:

Take two long data type integers lets say K and L to store sum of X and Y respectively, run a while loop till the sum difference is greater than or equal to zero. 

Follow the steps to solve the problem:

• Take two long data type variables let’s say K and L to store the sum of X[] and Y[] respectively till index i, other two integers A and B for output as discussed in the problem statement. 
• Take another variable Z, and initialize it to 0, Which will use to store the difference at index i as X[i] – Y[i]. Run a While loop till Z ≥ 0, and follow the below steps inside the loop :
  • Update the value of K and L.
  • Update the value of Z as Xi – Yi.
  • Increment A.
  • If Z is the maximum current value of the index at i, Then update B as i.
• Print the value of A and B.  

Below is the code to implement the above approach:

Time Complexity: O(A)
Auxiliary Space: O(1)  

Given an integer N (N ≥ 5) Then assume you have two infinite arrays X and Y where X[] is an array of element N and each element of Y[] is 2ⁱ where i is the index of the array, the task is to find two indices let’s say A and B which are the maximum value of the index at which the prefix sum in X[] is at least the same as the prefix sum of Y[] and the index value at which the X[i] – Y[i] is maximum respectively, Where The value of B should be less than or equal to A. Formally, B ≤ A.

Examples:

Input: N = 7
Output: A = 5, B = 3
Explanation: Y[] = {1, 2, 4, 8….., 2i – n}, X[] = {7, 7, 7, 7, …..7}
The sum of X[] till index 5 is: 35 
The sum of Y[] till index 5 is: 31
5 is the maximum value of index at which, The sum of elements of X[] is strictly greater than or equal to Y[]. Maximum possible difference of sum(Xi – Yi) is at index 3, Which is 14. Therefore, A = 5 and B = 3.

Input: N = 6
Output: A = 4, B = 3
Explanation: It can be verified that 4 is maximum possible value of index at which sum of elements of X[] is strictly greater than or equal to Y[] and max difference is at index 3. Therefore, A = 4 and B = 3.

Approach: Implement the idea below to solve the problem:

Take two long data type integers lets say K and L to store sum of X and Y respectively, run a while loop till the sum difference is greater than or equal to zero. 

Follow the steps to solve the problem:

• Take two long data type variables let’s say K and L to store the sum of X[] and Y[] respectively till index i, other two integers A and B for output as discussed in the problem statement. 
• Take another variable Z, and initialize it to 0, Which will use to store the difference at index i as X[i] – Y[i]. Run a While loop till Z ≥ 0, and follow the below steps inside the loop :
  • Update the value of K and L.
  • Update the value of Z as Xi – Yi.
  • Increment A.
  • If Z is the maximum current value of the index at i, Then update B as i.
• Print the value of A and B.  

Below is the code to implement the above approach:

Time Complexity: O(A)
Auxiliary Space: O(1)