Maximum index a pointer can reach in N steps by avoiding a given index B | Set 2
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++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// index the pointer can reach
int maximumIndex(int N, int B)
{
// Initialize two pointers
int i = 0, j = 1;
// Stores sum of first N
// natural numbers
int sum = N * (N + 1) / 2;
while (j <= N) {
// Increment i with j
i += j;
// Increment j with 1
j++;
// If i points to B
if (i == B) {
return sum - 1;
}
}
// return the pointer index
return sum;
}
// Driver Code
int main()
{
// Given value of N & B
int N = 4, B = 6;
// Function call to find maximum
// index the pointer can reach
cout << maximumIndex(N, B) << endl;
return 0;
}
// This code is modified by Susobhan Akhuli
class GFG {
// Function to find the maximum
// index the pointer can reach
static int maximumIndex(int N, int B)
{
// Stores sum of first N
// natural numbers
int sum = N * (N + 1) / 2;
int j = 1;
int i = 0;
while (j <= N) {
// Increment i with j
i += j;
// Increment j with 1
j++;
// If i points to B
if (i == B) {
return sum - 1;
}
}
// Return the pointer index
return sum;
}
// Driver Code
public 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
System.out.println(maximumIndex(N, B));
}
}
// This code is contributed by AnkThon
// This code is modified by Susobhan Akhuli
# Python3 program for the above approach
# Function to find the maximum
# index the pointer can reach
def maximumIndex(N, B):
# Initialize two pointers
i, j = 0, 1
# Stores sum of first N
# natural numbers
sum = N * (N + 1) // 2
while (j <= N):
# Increment i with j
i += j
# Increment j with 1
j += 1
# If i points to B
if (i == B):
return sum-1
# Return the pointer index
return sum
# Driver Code
if __name__ == '__main__':
# Given value of N & B
N, B = 4, 6
# Function call to find maximum
# index the pointer can reach
print(maximumIndex(N, B))
# This code is contributed by mohit kumar 29
# This code is modified by Susobhan Akhuli
// C# program for the above approach
using System;
class GFG {
// Function to find the maximum
// index the pointer can reach
static int maximumIndex(int N, int B)
{
// Initialize two pointers
int i = 0, j = 1;
// Stores sum of first N
// natural numbers
int sum = N * (N + 1) / 2;
while (j <= N) {
// Increment i with j
i += j;
// Increment j with 1
j++;
// If i points to B
if (i == B) {
return sum - 1;
}
}
// Return the pointer index
return sum;
}
// Driver Code
static public void Main()
{
// Given value of N & B
int N = 4, B = 6;
// Function call to find maximum
// index the pointer can reach
Console.Write(maximumIndex(N, B));
}
}
// This code is contributed by avijitmondal1998
// This code is modified by Susobhan Akhuli
// JavaScript program for the above approach
// Function to find the maximum
// index the pointer can reach
function maximumIndex(N, B)
{
// Initialize two pointers
let i = 0, j = 1;
// Stores sum of first N
// natural numbers
let sum = Math.floor(N * (N + 1) / 2);
while (j <= N) {
// Increment i with j
i += j;
// Increment j with 1
j++;
// If i points to B
if (i == B) {
return sum-1;
}
}
// Print the pointer index
return sum;
}
// Driver Code
// Given value of N & B
let N = 4, B = 6;
// Function call to find maximum
// index the pointer can reach
console.log(maximumIndex(N, B));
// This code is contributed by Surbhi Tyagi.
// This code is modified by Susobhan Akhuli
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:
#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;
}
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.
import math
def 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 False
def 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 & B
N = 3
B = 6
# Function call to find maximum
# index the pointer can reach
print(maximumIndex(N, B))
# this code is contributed by devendrasalunke
// C# code to implement the approach
using 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
function isNaturalSum(B) {
var 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 false;
}
}
function maximumIndex(N, B) {
// Maximum Reachable value with N steps
var 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_sum
if (is_B_reachable) {
return max_sum - 1;
} else {
return max_sum;
}
}
// Given value of N & B
var N = 3;
var B = 6;
// Function call to find maximum
// index the pointer can reach
console.log(maximumIndex(N, B));
// This code is contributed by phasing17.
Output
5
Time Complexity: O(1)
Auxiliary Space: O(1)