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 2i 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:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;static void calculateIndices(int N){ // Variable to store difference at // each iteration of while Loop long Z = 0; // Counter for calculating // power of 2 long Pow_counter = 1; // Variable K to store sum of // elements of X[] long K = 0; // Variable K to store sum of // elements of X[] long L = 0; // Variable to store Max value of // index at which Z >= 0 long A = 0; // Variable to store Max value of // index at which Z is maximum in // all iterations of while loop long B = 0; // max variable to store maximum // value of Z long max = LONG_MIN; // While loop to execute // till Z >= 0 while (Z >= 0) { // Updating value of K K += N; // Updating value of L L += pow(2, Pow_counter - 1); // Incrementing A A++; // Updating value of Z Z = K - L; // If Z is maxed till now if (Z > max) { // Update max variable as Z max = Z; // Update B as max_counter B = Pow_counter; } // Incrementing variable // Pow_counter, if Z is // non-negative(Z >= 0) if (Z >= 0) Pow_counter++; } // Printing value of Z cout << (A - 1) << " " << B << endl;}// Driver codeint main(){ long N = 6; calculateIndices(N); return 0;}// This code is contributed by Tapesh(tapeshdua420) |
Java
// Java code for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { static void calculateIndices(long N) { // Variable to store difference at // each iteration of while Loop long Z = 0; // Counter for calculating // power of 2 long Pow_counter = 1; // Variable K to store sum of // elements of X[] long K = 0; // Variable K to store sum of // elements of X[] long L = 0; // Variable to store Max value of // index at which Z >= 0 long A = 0; // Variable to store Max value of // index at which Z is maximum in // all iterations of while loop long B = 0; // max variable to store maximum // value of Z long max = Long.MIN_VALUE; // While loop to execute // till Z >= 0 while (Z >= 0) { // Updating value of K K += N; // Updating value of L L += Math.pow(2, Pow_counter - 1); // Incrementing A A++; // Updating value of Z Z = K - L; // If Z is maxed till now if (Z > max) { // Update max variable as Z max = Z; // Update B as max_counter B = Pow_counter; } // Incrementing variable // Pow_counter, if Z is // non-negative(Z >= 0) if (Z >= 0) Pow_counter++; } // Printing value of Z System.out.println((A - 1) + " " + B); } // Driver code public static void main(String args[]) { long N = 6; calculateIndices(N); }} |
Python3
# Python code for the above approachimport math# Function to calculate indicesdef calculateIndices(N): # Variable to store difference at # each iteration of while Loop Z = 0 # Counter for calculating # power of 2 Pow_counter = 1 # Variable K to store sum of # elements of X[] K = 0 # Variable K to store sum of # elements of X[] L = 0 # Variable to store Max value of # index at which Z >= 0 A = 0 # Variable to store Max value of # index at which Z is maximum in # all iterations of while loop B = 0 # max variable to store maximum # value of Z max = -math.inf # While loop to execute # till Z >= 0 while (Z >= 0): # Updating value of K K += N # Updating value of L L += pow(2, Pow_counter - 1) # Incrementing A A += 1 # Updating value of Z Z = K - L # If Z is maxed till now if (Z > max): # Update max variable as Z max = Z # Update B as max_counter B = Pow_counter # Incrementing variable # Pow_counter, if Z is # non-negative(Z >= 0) if (Z >= 0): Pow_counter += 1 # Printing value of Z print(A - 1, B)# Driver codeN = 6calculateIndices(N)# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code for the above approachusing System;public class GFG{ static void calculateIndices(long N) { // Variable to store difference at // each iteration of while Loop long Z = 0; // Counter for calculating // power of 2 long Pow_counter = 1; // Variable K to store sum of // elements of X[] long K = 0; // Variable K to store sum of // elements of X[] long L = 0; // Variable to store Max value of // index at which Z >= 0 long A = 0; // Variable to store Max value of // index at which Z is maximum in // all iterations of while loop long B = 0; // max variable to store maximum // value of Z long max = Int64.MinValue; // While loop to execute // till Z >= 0 while (Z >= 0) { // Updating value of K K += N; // Updating value of L L += (long)Math.Pow(2, Pow_counter - 1); // Incrementing A A++; // Updating value of Z Z = K - L; // If Z is maxed till now if (Z > max) { // Update max variable as Z max = Z; // Update B as max_counter B = Pow_counter; } // Incrementing variable // Pow_counter, if Z is // non-negative(Z >= 0) if (Z >= 0) Pow_counter++; } // Printing value of Z Console.WriteLine((A - 1) + " " + B); } static public void Main (){ // Code long N = 6; calculateIndices(N); }}// This code is contributed by lokeshmvs21. |
Javascript
<script> // JavaScript code for the above approach function calculateIndices(N) { // Variable to store difference at // each iteration of while Loop var Z = 0; // Counter for calculating // power of 2 var Pow_counter = 1; // Variable K to store sum of // elements of X[] var K = 0; // Variable K to store sum of // elements of X[] var L = 0; // Variable to store Max value of // index at which Z >= 0 var A = 0; // Variable to store Max value of // index at which Z is maximum in // all iterations of while loop var B = 0; // max variable to store maximum // value of Z var max = -Infinity; // While loop to execute // till Z >= 0 while (Z >= 0) { // Updating value of K K += N; // Updating value of L L += Math.pow(2, Pow_counter - 1); // Incrementing A A += 1; // Updating value of Z Z = K - L; // If Z is maxed till now if (Z > max) { // Update max variable as Z max = Z; // Update B as max_counter B = Pow_counter; } // Incrementing variable // Pow_counter, if Z is // non-negative(Z >= 0) if (Z >= 0) { Pow_counter += 1; } } // Printing value of Z console.log(A - 1, B); } // Driver code var N = 6; calculateIndices(N); // This code is contributed by Tapesh(tapeshdua420)</script> |
Output
4 3
Time Complexity: O(A)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
