Найдите максимальное значение индексов массива, удовлетворяющих заданным условиям

Учитывая целое число N (N ≥ 5). Затем предположим, что у вас есть два бесконечных массива X и Y , где X[] — массив элементов N , а каждый элемент Y[] равен 2 ⁱ , где i — индекс массива, задача состоит в том, чтобы найти два индекса, скажем, A и B , которые являются максимальное значение индекса, при котором сумма префиксов в X[] не меньше суммы префиксов Y[] и значение индекса, при котором X[i] – Y[i] максимальны соответственно, где значение B должно быть меньше или равно A. Формально B ≤ A .

Примеры:

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.

Подход: Реализуйте идею ниже, чтобы решить проблему:

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. 

Следуйте инструкциям, чтобы решить проблему:

• Возьмите две длинные переменные типа данных, скажем, K и L, чтобы сохранить сумму X[] и Y[] соответственно до индекса i, два других целых числа A и B для вывода, как описано в постановке задачи.
• Возьмите другую переменную Z и инициализируйте ее значением 0, которое будет использоваться для хранения разницы в индексе i как X[i] – Y[i]. Запустите цикл While до Z ≥ 0 и выполните следующие шаги внутри цикла:
  • Обновите значение K и L.
  • Обновите значение Z как Xi – Yi.
  • Приращение А.
  • Если Z является максимальным текущим значением индекса в i, то обновите B как i.
• Выведите значение A и B .

Ниже приведен код для реализации вышеуказанного подхода:

Временная сложность: O(A)
Вспомогательное пространство: O(1)