Given two integers N and B, the task is to print the maximum index in an array that can be reached, starting from the 0th index, in N steps without placing itself at index B at any point, where in every ith step, pointer can move i indices to the right.
Examples:
Input: N = 4, B = 6
Output: 9
Explanation: Following sequence of moves maximizes the index that can be reached.
- Step 1: Initially, pos = 0. Remain in the same position.
- Step 2: Move 2 indices to the right. Therefore, current position = 0 + 2 = 2.
- Step 3: Move 3 indices to the right. Therefore, current position = 2 + 3 = 5.
- Step 4: Move 4 indices to the right. Therefore, current position = 5 + 4 = 9.
Input: N = 2, B = 2
Output: 3
Naive Approach: Refer to the previous post for the simplest approach to solve the problem.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The most optimal idea to solve the problem is based on the following observations:
Observation:
- If observed carefully, the answer is either the sequence from the arithmetic sum of steps or that of the arithmetic sum of steps – 1.
- This is because, the highest possible number without considering B, is reachable by not waiting (which would give the arithmetic sum).
- But if B is a part of that sequence, then waiting at 0 in the first steps ensures that the sequence does not intersect with the sequence obtained without waiting (as it is always 1 behind).
- Any other sequence (i.e waiting at any other point once or more number of times) will always yield a smaller maximum reachable index.
Follow the steps below to solve the problem:
- Initialize two pointers i = 0 and j = 1.
- Initialize a variable, say sum, to store the sum of first N natural numbers, i.e. N * (N + 1) / 2.
- Initialize a variable, say cnt = 0 and another variable, say flag = false.
- Iterate until cnt is less than N.
- Increment i with j.
- Increment j.
- Increment cnt.
- If at any iteration, i is equal to B, set flag = true and break out of the loop.
- If flag is false, then print sum. Otherwise, print sum – 1.
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 the pointer can reachint maximumIndex(int N, int B){ // Initialize two pointers int i = 0, j = 1; // Stores number of steps int cnt = 0; // Stores sum of first N // natural numbers int sum = N * (N + 1) / 2; bool flag = false; while (cnt < N) { // Increment i with j i += j; // Increment j with 1 j++; // Increment count cnt++; // If i points to B if (i == B) { // Break flag = true; break; } } // Print the pointer index if (!flag) { cout << sum; } else cout << sum - 1;}// Driver Codeint main(){ // Given value of N & B int N = 4, B = 6; // Function call to find maximum // index the pointer can reach maximumIndex(N, B); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to find the maximum// index the pointer can reachstatic void maximumIndex(int N, int B){ // Initialize two pointers int i = 0, j = 1; // Stores number of steps int cnt = 0; // Stores sum of first N // natural numbers int sum = N * (N + 1) / 2; boolean flag = false; while (cnt < N) { // Increment i with j i += j; // Increment j with 1 j++; // Increment count cnt++; // If i points to B if (i == B) { // Break flag = true; break; } } // Print the pointer index if (!flag == true) { System.out.print(sum); } else { System.out.print(sum - 1); }}// Driver Codepublic static void main (String[] args){ // Given value of N & B int N = 4, B = 6; // Function call to find maximum // index the pointer can reach maximumIndex(N, B);}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find the maximum# index the pointer can reachdef maximumIndex(N, B): # Initialize two pointers i, j = 0, 1 # Stores number of steps cnt = 0 # Stores sum of first N # natural numbers sum = N * (N + 1) // 2 flag = False while (cnt < N): # Increment i with j i += j # Increment j with 1 j += 1 # Increment count cnt += 1 # If i points to B if (i == B): # Break flag = True break # Print the pointer index if (not flag): print (sum) else: print(sum - 1)# Driver Codeif __name__ == '__main__': # Given value of N & B N, B = 4, 6 # Function call to find maximum # index the pointer can reach maximumIndex(N, B)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum// index the pointer can reachstatic void maximumIndex(int N, int B){ // Initialize two pointers int i = 0, j = 1; // Stores number of steps int cnt = 0; // Stores sum of first N // natural numbers int sum = N * (N + 1) / 2; bool flag = false; while (cnt < N) { // Increment i with j i += j; // Increment j with 1 j++; // Increment count cnt++; // If i points to B if (i == B) { // Break flag = true; break; } } // Print the pointer index if (!flag == true) { Console.Write(sum); } else { Console.Write(sum - 1); }}// Driver Codestatic public void Main (){ // Given value of N & B int N = 4, B = 6; // Function call to find maximum // index the pointer can reach maximumIndex(N, B);}}// This code is contributed by avijitmondal1998 |
Javascript
<script>// JavaScript program for the above approach// Function to find the maximum// index the pointer can reachfunction maximumIndex(N, B){ // Initialize two pointers let i = 0, j = 1; // Stores number of steps let cnt = 0; // Stores sum of first N // natural numbers let sum = Math.floor(N * (N + 1) / 2); let flag = false; while (cnt < N) { // Increment i with j i += j; // Increment j with 1 j++; // Increment count cnt++; // If i points to B if (i == B) { // Break flag = true; break; } } // Print the pointer index if (!flag) { document.write(sum); } else document.write(sum - 1);}// Driver Code // Given value of N & B let N = 4, B = 6; // Function call to find maximum // index the pointer can reach maximumIndex(N, B);// This code is contributed by Surbhi Tyagi.</script> |
Output
9
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Efficient Approach:
In the previous approach, we have established that the minimum value can never be less than the (total sum of N natural number) – 1.
In this approach, we will try to find if B can occur in any of the steps in a more optimal way.
- The idea is to use the quadratic equation formula to retrieve if there exists a valid number x for which (x)(x+1)/2 = B.
- Since, B is already given, we can rewrite the equation as x2 + x – 2B = 0.
- Using the quadratic formula, we can identify if x is a valid integer which satisfies this condition.
- If find a valid x, we can return (N)(N+1)/2 – 1. Else, we can directly return (N)(N+1)/2.
Below is the implementation of the approach discussed:
C++
#include <iostream>#include <math.h>using namespace std;bool isNaturalSum(int B){ float x=(-1+sqrt(1+8*B))/2; //check for valid integer value of x if(ceil(x)==floor(x)) return true; else return false;}int maximumIndex(int N, int B){ //Maximum Reachable value with N steps long long int max_sum = ((N)*(N+1))/2; //Determine if B lies in the sum of x natural numbers. bool is_B_reachable = isNaturalSum(B); //If B is reachable, don't include the first step else return the max_sum if(is_B_reachable){ return max_sum - 1; } else{ return max_sum; }}int main(){ // Given value of N & B int N = 3, B = 6; // Function call to find maximum // index the pointer can reach cout<<maximumIndex(N, B)<<endl; return 0;} |
Java
import java.util.*;public class GFG { public static boolean isNaturalSum(int B) { double x = (-1 + Math.sqrt(1 + 8 * B)) / 2; // check for valid integer value of x return Math.ceil(x) == Math.floor(x); } public static int maximumIndex(int N, int B) { // Maximum Reachable value with N steps int maxSum = (N * (N + 1)) / 2; // Determine if B lies in the sum of x natural numbers. boolean isBReachable = isNaturalSum(B); // If B is reachable, don't include the first step else return the max_sum return isBReachable? maxSum - 1 : maxSum; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // Given value of N & B int N = 3; int B = 6; // Function call to find maximum // index the pointer can reach System.out.println(maximumIndex(N, B)); scanner.close(); }}// This code is contributed by aadityaburujwale. |
Python3
import mathdef isNaturalSum(B): x = (-1 + math.sqrt(1 + 8*B))/2 # check for valid integer value of x if math.ceil(x) == math.floor(x): return True else: return Falsedef maximumIndex(N, B): # Maximum Reachable value with N steps max_sum = ((N)*(N+1))//2 # Determine if B lies in the sum of x natural numbers. is_B_reachable = isNaturalSum(B) # If B is reachable, don't include the first step else return the max_sum if is_B_reachable: return max_sum - 1 else: return max_sum# Given value of N & BN = 3B = 6# Function call to find maximum# index the pointer can reachprint(maximumIndex(N, B))# this code is contributed by devendrasalunke |
Javascript
function isNaturalSum(B) {var x = (-1 + Math.sqrt(1 + 8 * B)) / 2;// check for valid integer value of xif (Math.ceil(x) === Math.floor(x)) { return true;} else { return false;}}function maximumIndex(N, B) {// Maximum Reachable value with N stepsvar max_sum = (N * (N + 1)) / 2;// Determine if B lies in the sum of x natural numbers.var is_B_reachable = isNaturalSum(B);// If B is reachable, don't include the first step else return the max_sumif (is_B_reachable) { return max_sum - 1;} else { return max_sum;}}// Given value of N & Bvar N = 3;var B = 6;// Function call to find maximum// index the pointer can reachconsole.log(maximumIndex(N, B));// This code is contributed by phasing17. |
C#
// C# code to implement the approachusing System;class GFG{ public static bool IsNaturalSum(int B) { double x = (-1 + Math.Sqrt(1 + 8 * B)) / 2; // check for valid integer value of x return Math.Ceiling(x) == Math.Floor(x); } public static int MaximumIndex(int N, int B) { // Maximum Reachable value with N steps int maxSum = (N * (N + 1)) / 2; // Determine if B lies in the sum of x natural numbers. bool isBReachable = IsNaturalSum(B); // If B is reachable, don't include the first step else return the max_sum return isBReachable ? maxSum - 1 : maxSum; } public static void Main(string[] args) { // Given value of N & B int N = 3; int B = 6; // Function call to find maximum // index the pointer can reach Console.WriteLine(MaximumIndex(N, B)); }} // This code is contributed by phasing17 |
Output
5
Time Complexity: O(1)
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!
