Maximum index a pointer can reach in N steps by avoiding a given index B | Set 2

0 0 9 minutes read

Given two integers N and B, the task is to print the maximum index in an array that can be reached, starting from the 0^th index, in N steps without placing itself at index B at any point, where in every i^th 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(N³)
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 reach
int 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 Code
int 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 approach
class GFG{
     
// Function to find the maximum
// index the pointer can reach
static 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 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
    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 reach
def 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 Code
if __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 approach
using System;
 
class GFG{
     
// Function to find the maximum
// index the pointer can reach
static 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 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
    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 reach
function 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

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 x² + 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 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

Javascript

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.

C#

// 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

Output

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 zambiatek!