Максимальный индекс, которого указатель может достичь за N шагов, избегая заданного индекса B — набор 3 (бинарный поиск)

Даны два целых числа N и B , задача состоит в том, чтобы напечатать максимальный индекс, которого может достичь указатель, начиная с 0 ^-го индекса, в массиве натуральных чисел (т. е. 0, 1, 2, 3, 4, 5…), скажем, arr [] , за N шагов, не помещая себя в индекс B в любой точке.

 In each step, the pointer can move from the Current Index to a Jumping Index or can remain at the Current Index. 
Jumping Index = Current Index + Step Number

Примеры:

Input: N = 3, B = 2
Output: 6
Explanation:

Step 1:
Current Index = 0
Step Number = 1
Jumping Index = 0 + 1 = 1
Step 2:Current Index = 1
Step Number = 2
Jumping Index = 1 + 2 = 3
Step 3:
Current Index = 3
Step Number = 3
Jumping Index = 3 + 3 = 6
Therefore, the maximum index that can be reached is 6.

Input: N = 3, B = 1
Output: 5
Explanation: 

Step 1:
Current Index = 0
Step Number = 1
Jumping Index = 0 + 1 = 1But this is bad index. So pointer remains at the Current Index.
Step 2:
Current Index = 0
Step Number = 2
Jumping Index = 0 + 2 = 2
Step 3:
Current Index = 2
Step Number = 3
Jumping Index = 2 + 3 = 5
Therefore, the maximum index that can be reached is 5.

Эффективный подход . Наивный подход, обсуждаемый в этой статье, также можно оптимизировать с помощью бинарного поиска. Если значение maxIndex – B существует в сумме любых последних K чисел из первых N натуральных чисел, то maxIndex не может быть уменьшен до меньшего, чем равный 0 , без скачка по индексу B . поэтому уменьшите максимальный индекс на и повторите описанные выше шаги. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную maxIndexReached как 0 .
• Инициализируйте вектор Ans[] .
• Переберите диапазон [1, N], используя переменную i , добавьте значение i к переменной maxIndexReached и поместите значение i в вектор Ans[] .
• Обратить вектор Ans[].
• Переберите диапазон [1, Ans.size()) с помощью переменной i и добавьте значение Ans[i – 1] к Ans[i] .
• Пройдите через цикл while, пока maxIndexReached не станет больше 0 , и выполните следующие задачи:
  • Инициализируйте переменную auto как указатель, значение которого больше или равно maxIndexReached – B в массиве Ans[] .
  • Если он равен Ans.end() , то выйти из цикла.
  • Если *it равно maxIndexReached – B , то значение maxIndexReached уменьшается на 1 . В противном случае вырваться из цикла.
• После выполнения вышеуказанных шагов выведите в качестве ответа значение maxIndexReached .

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

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