Maximum index a pointer can reach in N steps by avoiding a given index B β Set 3 (Binary Search)
Given two integers N and B, the task is to print the maximum index a pointer, starting from 0th index can reach in an array of natural numbers(i.e., 0, 1, 2, 3, 4, 5β¦), say arr[], in N steps without placing itself at index B at any point.
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
Examples:
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.
Efficient Approach: The naive approach discussed in this article can also be optimized by using Binary Search. If the value of maximumIndex β B exists in the sum of any last K numbers from the first N natural numbers then the maximumIndex canβt be reduced to less than equal to 0 without the jump on index B. therefore, decrement the maximum Index by and perform the above steps again. Follow the steps below to solve the problem:
- Initialize the variable maximumIndexReached as 0.
- Initialize the vector Ans[].
- Iterate over the range [1, N] using the variable i and add the value i to the variable maximumIndexReached and push the value i into the vector Ans[].
- Reverse the vector Ans[].
- Iterate over the range [1, Ans.size()) using the variable i and add the value Ans[i β 1] to Ans[i].
- Traverse over a while loop till maximumIndexReached is greater than 0 and perform the following tasks:
- Initialize an auto variable it as the pointer whose value is greater than or equal to maximumIndexReached β B in the array Ans[].
- If it equals Ans.end() then break out of the loop.
- If *it equals maximumIndexReached β B then decreases the value of maximumIndexReached by 1. Otherwise, break out of the loop.
- After performing the above steps, print the value of maximumIndexReached as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum index // reachable int maxIndex( int N, int B) { // Store the answer int maximumIndexReached = 0; vector< int > Ans; // Store the maximum index possible // i.e, N*(N-1) for ( int i = 1; i <= N; i++) { maximumIndexReached += i; Ans.push_back(i); } reverse(Ans.begin(), Ans.end()); // Add the previous elements for ( int i = 1; i < ( int )Ans.size(); i++) { Ans[i] += Ans[i - 1]; } // Run a loop while (maximumIndexReached) { // Binary Search auto it = lower_bound(Ans.begin(), Ans.end(), maximumIndexReached - B); if (it == Ans.end()) { break ; } if (*it == maximumIndexReached - B) { maximumIndexReached--; } else { break ; } } return maximumIndexReached; } // Driver Code int main() { int N = 3, B = 2; cout << maxIndex(N, B); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the maximum index // reachable static int maxIndex( int N, int B) { // Store the answer int maximumIndexReached = 0 ; Vector<Integer> Ans = new Vector<>(); // Store the maximum index possible // i.e, N*(N-1) for ( int i = 1 ; i <= N; i++) { maximumIndexReached += i; Ans.add(i+i- 1 ); } // Run a loop while (maximumIndexReached> 0 ) { // Binary Search int it = lower_bound(Ans, maximumIndexReached - B); if (it == - 1 ) { break ; } if (it == maximumIndexReached - B) { maximumIndexReached--; } else { break ; } } return maximumIndexReached; } public static int lower_bound(Vector<Integer> s, int val) { List<Integer> temp = new LinkedList<Integer>(); temp.addAll(s); Collections.sort(temp); Collections.reverse(temp); if (temp.indexOf(val) + 1 == temp.size()) return - 1 ; else if (temp.get(temp.indexOf(val) + 1 )>val) return - 1 ; else return temp.get(temp.indexOf(val) + 1 ); } // Driver Code public static void main(String[] args) { int N = 3 , B = 2 ; System.out.print(maxIndex(N, B)); } } // This code is contributed by Rajput-Ji |
Python3
# Python 3 program for the above approach from bisect import bisect_left # Function to find the maximum index # reachable def maxIndex(N, B): # Store the answer maximumIndexReached = 0 Ans = [] # Store the maximum index possible # i.e, N*(N-1) for i in range ( 1 , N + 1 ): maximumIndexReached + = i Ans.append(i) Ans.reverse() # Add the previous elements for i in range ( len (Ans)): Ans[i] + = Ans[i - 1 ] # Run a loop while (maximumIndexReached): # Binary Search it = bisect_left(Ans, maximumIndexReached - B) if (it not in Ans): break if (it = = maximumIndexReached - B): maximumIndexReached - = 1 else : break return maximumIndexReached # Driver Code if __name__ = = "__main__" : N = 3 B = 2 print (maxIndex(N, B)) # This code is contributed by ukasp. |
C#
using System; using System.Linq; using System.Collections.Generic; class GFG { // Function to find the maximum index // reachable static int maxIndex( int N, int B) { // Store the answer int maximumIndexReached = 0; List< int > Ans = new List< int >(); // Store the maximum index possible // i.e, N*(N-1) for ( int i = 1; i <= N; i++) { maximumIndexReached += i; Ans.Add(i + i - 1); } // Run a loop while (maximumIndexReached > 0) { // Binary Search int it = Ans.Where(x => x <= maximumIndexReached - B).DefaultIfEmpty(-1).Max(); if (it == -1) { break ; } if (it == maximumIndexReached - B) { maximumIndexReached--; } else { break ; } } return maximumIndexReached; } // Driver Code public static void Main() { int N = 3, B = 2; Console.WriteLine(maxIndex(N, B)); } } |
Javascript
<script> // JavaScript Program to implement // the above approach function lowerBound(Ans, target) { const targetRange = [-1, -1] const leftIdx = extremeInsertionIndex(Ans, target, true ) if (leftIdx === Ans.length || Ans[leftIdx] != target) return targetRange targetRange[0] = leftIdx targetRange[1] = extremeInsertionIndex(Ans, target, false ) - 1 return targetRange function extremeInsertionIndex(Ans, target, left) { let lo = 0, hi = Ans.length while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2) if (Ans[mid] > target || (left && target === Ans[mid])) hi = mid else lo = mid + 1 } return lo } } // Function to find the maximum index // reachable function maxIndex(N, B) { // Store the answer let maximumIndexReached = 0; let Ans = []; // Store the maximum index possible // i.e, N*(N-1) for (let i = 1; i <= N; i++) { maximumIndexReached += i; Ans.push(i); } Ans.reverse(); // Add the previous elements for (let i = 1; i < Ans.length; i++) { Ans[i] += Ans[i - 1]; } // Run a loop while (maximumIndexReached) { // Binary Search let it = lowerBound(Ans, maximumIndexReached - B); if (it == -1) { break ; } if (it == maximumIndexReached - B) { maximumIndexReached--; } else { break ; } } return maximumIndexReached; } // Driver Code let N = 3, B = 2; document.write(maxIndex(N, B)); // This code is contributed by Potta Lokesh </script> |
6
Time Complexity: O(N*log N)
Auxiliary Space: O(N)