Given a number line having integer points 0 to N+1, where we are currently at point 0. Given K coins and an array arr[] of size N, such that arr[i] = jump cost for point (i + 1), 0 <= i < N. From any point i, we can move 1 unit left or 1 unit right using 1 coin, or jump to point 0 or N + 1 using arr[i] coins. The task is to find the maximum number of jumps we can perform such that we can jump from any index at max once.

Examples:

Input: N = 5, K = 6, arr[]= {1, 1, 1, 1, 1}
Output: 2
Explanation:

• We can move one unit to the right, use the jump at point 1 and move to point N + 1 = point 6, cost = 1 + 1 = 2.
• Move one unit to the left and use the jump at point 5, cost = 1 + 1 = 2.

Now, we are left with 6 – 2 – 2 = 2 coins, and wherever we jump, we won’t have enough coins to perform another jump. So, the answer is 2.

Input: N = 4, K = 10, arr[] = {2, 2, 2, 2, 2}
Output: 3
Explanation:

• We can move one unit to the right, use the jump at point 1 and move to point N + 1 = point 5, cost = 1 + 2 = 3.
• We can move one unit to the left, use the jump at point 4 and move to point 0, cost = 1 + 2 = 3.
• We can move two units to the right, use the jump at point 2, cost = 2 + 2 = 4.

Now, we are left with 10 – 3 – 3 – 4 = 0 coins, and wherever we jump, we won’t have enough coins to perform another jump. So, the answer is 3.

Approach: To solve the problem, follow the below idea:

If we observe carefully, the total cost to jump from a point i is min(arr[i] + i + 1, arr[i] + N – i) as there are two ways to reach the point i, either from the point 0 with cost = (i + 1) or from the point (N + 1) with cost = (N – i) and the cost to jump from the ith point is arr[i]. Now, in order to maximize the total number of jumps, we can choose a greedy approach and jump from those points first which have lower total cost.

It is to be noted that all the points can be reached either from point 0 or from point (N + 1), except the point which we choose in the beginning to jump from as that point can be reached only through point 0 (We are standing at point 0 initially). So, we can iterate over all the points considering each of them as the beginning point and then calculate the jumps in all the cases. Maximum jumps among all the cases will be our answer.

In order to calculate the number of jumps for a particular point, we can use Binary Search on the prefix sum array, say prefSum, where the prefixSum[i] stores the maximum cost to jump till ith smallest point. For eg: prefSum[0] stores the minimum cost to jump from the point having the smallest cost, prefSum[1] stores the minimum cost to jump from the point having the second smallest cost and so on.

Step-by-step algorithm:

• Initialize a vector of pairs to store the minimum cost to reach point i either from point 0 or from point (N + 1) along with the cost to reach the point i from point 0.
• Sort the cost[] vector according to the minimum cost to reach the point.
• Maintain a prefix sum array, say prefSums, to apply Binary Search on it and calculate the total cost to jump any number of points with smallest cost in log(N) time.
• Iterate over all the points, choose every point as the starting point and calculate the maximum number of jumps corresponding to each of the starting point.
• Return the maximum among all the jumps as the final answer.

Below is the implementation of the algorithm:

#include <bits/stdc++.h>
using namespace std;

int solve(int N, int K, vector<int>& arr)
{
    // vector to store the pair of {minimum cost to reach
    // the point either from point 0 or from point (N + 1),
    // cost to reach the index from point 0}
    vector<pair<int, int> > cost;
    for (int i = 0; i < N; i++) {
        cost.push_back(
            { min(arr[i] + i + 1, arr[i] + N - i),
            arr[i] + i + 1 });
    }

    // sort the cost according to the min cost to reach the
    // point either from point 0 or from point (N + 1)
    sort(cost.begin(), cost.end());

    // vector to store the prefix sum of the total cost to
    // jump from i points having the smallest cost
    vector<int> prefSum;
    prefSum.push_back(0);

    for (int i = 0; i < N; i++) {
        prefSum.push_back(prefSum[i] + cost[i].first);
    }

    // Variable to store the maximum jumps across all the
    // starting points
    int ans = 0;

    for (int i = 0; i < N; i++) {
        // Assume that we start with ith point, so we reach
        // ith point from point 0

        // Remaining cost after choosing the ith point as
        // the starting point
        int remainingCost = K - cost[i].second;

        // Initializing the range of jumps
        int low = 0, high = N;

        // Variable to store the maximum jumps with ith
        // point being the starting point
        int maxJumps = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            int price = prefSum[mid];
            int currJumps = mid + 1;

            // If the starting point is in the current
            // range, then remove the extra cost of the
            // starting point
            if (mid > i) {
                price -= cost[i].first;
                currJumps -= 1;
            }

            // If the current price is less than or equal to
            // the remaining cost, then it means we can have
            // mid number of jumps
            if (price <= remainingCost) {
                maxJumps = max(maxJumps, currJumps);
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
        ans = max(ans, maxJumps);
    }
    return ans;
}

int main()
{
    int N = 5, K = 6;
    vector<int> arr = { 1, 1, 1, 1, 1 };
    cout << solve(N, K, arr) << "\n";

    return 0;
}

import java.util.*;

public class Main {
    public static int solve(int N, int K, int[] arr) {
        // Array to store the pair of {minimum cost to reach
        // the point either from point 0 or from point (N + 1),
        // cost to reach the index from point 0}
        Pair[] cost = new Pair[N];
        for (int i = 0; i < N; i++) {
            cost[i] = new Pair(Math.min(arr[i] + i + 1, arr[i] + N - i), arr[i] + i + 1);
        }

        // Sort the cost according to the min cost to reach the
        // point either from point 0 or from point (N + 1)
        Arrays.sort(cost);

        // Array to store the prefix sum of the total cost to
        // jump from i points having the smallest cost
        int[] prefSum = new int[N+1];
        prefSum[0] = 0;

        for (int i = 0; i < N; i++) {
            prefSum[i+1] = prefSum[i] + cost[i].first;
        }

        // Variable to store the maximum jumps across all the
        // starting points
        int ans = 0;

        for (int i = 0; i < N; i++) {
            // Assume that we start with ith point, so we reach
            // ith point from point 0

            // Remaining cost after choosing the ith point as
            // the starting point
            int remainingCost = K - cost[i].second;

            // Initializing the range of jumps
            int low = 0, high = N;

            // Variable to store the maximum jumps with ith
            // point being the starting point
            int maxJumps = 0;
            while (low <= high) {
                int mid = (low + high) / 2;
                int price = prefSum[mid];
                int currJumps = mid + 1;

                // If the starting point is in the current
                // range, then remove the extra cost of the
                // starting point
                if (mid > i) {
                    price -= cost[i].first;
                    currJumps -= 1;
                }

                // If the current price is less than or equal to
                // the remaining cost, then it means we can have
                // mid number of jumps
                if (price <= remainingCost) {
                    maxJumps = Math.max(maxJumps, currJumps);
                    low = mid + 1;
                }
                else {
                    high = mid - 1;
                }
            }
            ans = Math.max(ans, maxJumps);
        }
        return ans;
    }

    public static void main(String[] args) {
        int N = 5, K = 6;
        int[] arr = { 1, 1, 1, 1, 1 };
        System.out.println(solve(N, K, arr));
    }

    static class Pair implements Comparable<Pair> {
        int first, second;

        Pair(int a, int b) {
            first = a;
            second = b;
        }

        @Override
        public int compareTo(Pair o) {
            return this.first - o.first;
        }
    }
}

# Python Implementation

def solve(N, K, arr):
    # List to store the pair of {minimum cost to reach
    # the point either from point 0 or from point (N + 1),
    # cost to reach the index from point 0}
    cost = [(min(arr[i] + i + 1, arr[i] + N - i), arr[i] + i + 1) for i in range(N)]

    # Sort the cost according to the min cost to reach the
    # point either from point 0 or from point (N + 1)
    cost.sort()

    # List to store the prefix sum of the total cost to
    # jump from i points having the smallest cost
    prefSum = [0]
    for i in range(N):
        prefSum.append(prefSum[i] + cost[i][0])

    # Variable to store the maximum jumps across all the
    # starting points
    ans = 0

    for i in range(N):
        # Assume that we start with ith point, so we reach
        # ith point from point 0

        # Remaining cost after choosing the ith point as
        # the starting point
        remainingCost = K - cost[i][1]

        # Initializing the range of jumps
        low, high = 0, N

        # Variable to store the maximum jumps with ith
        # point being the starting point
        maxJumps = 0
        while low <= high:
            mid = (low + high) // 2
            price = prefSum[mid]
            currJumps = mid + 1

            # If the starting point is in the current
            # range, then remove the extra cost of the
            # starting point
            if mid > i:
                price -= cost[i][0]
                currJumps -= 1

            # If the current price is less than or equal to
            # the remaining cost, then it means we can have
            # mid number of jumps
            if price <= remainingCost:
                maxJumps = max(maxJumps, currJumps)
                low = mid + 1
            else:
                high = mid - 1
        ans = max(ans, maxJumps)
    return ans

if __name__ == "__main__":
    N = 5
    K = 6
    arr = [1, 1, 1, 1, 1]
    print(solve(N, K, arr))


# This code is contributed by Sakshi

using System;
using System.Collections.Generic;

class GFG
{
    static int Solve(int N, int K, List<int> arr)
    {
        // List to store the pair of {minimum cost to reach
        // the point either from point 0 or from point (N + 1),
        // cost to reach the index from point 0}
        List<(int, int)> cost = new List<(int, int)>();
        for (int i = 0; i < N; i++)
        {
            cost.Add(
                (Math.Min(arr[i] + i + 1, arr[i] + N - i),
                arr[i] + i + 1));
        }

        // Sort the cost according to the min cost to reach the
        // point either from point 0 or from point (N + 1)
        cost.Sort();

        // List to store the prefix sum of the total cost to
        // jump from i points having the smallest cost
        List<int> prefSum = new List<int>();
        prefSum.Add(0);

        for (int i = 0; i < N; i++)
        {
            prefSum.Add(prefSum[i] + cost[i].Item1);
        }

        // Variable to store the maximum jumps across all the
        // starting points
        int ans = 0;

        for (int i = 0; i < N; i++)
        {
            // Assume that we start with ith point, so we reach
            // ith point from point 0

            // Remaining cost after choosing the ith point as
            // the starting point
            int remainingCost = K - cost[i].Item2;

            // Initializing the range of jumps
            int low = 0, high = N;

            // Variable to store the maximum jumps with ith
            // point being the starting point
            int maxJumps = 0;
            while (low <= high)
            {
                int mid = (low + high) / 2;
                int price = prefSum[mid];
                int currJumps = mid + 1;

                // If the starting point is in the current
                // range, then remove the extra cost of the
                // starting point
                if (mid > i)
                {
                    price -= cost[i].Item1;
                    currJumps -= 1;
                }

                // If the current price is less than or equal to
                // the remaining cost, then it means we can have
                // mid number of jumps
                if (price <= remainingCost)
                {
                    maxJumps = Math.Max(maxJumps, currJumps);
                    low = mid + 1;
                }
                else
                {
                    high = mid - 1;
                }
            }
            ans = Math.Max(ans, maxJumps);
        }
        return ans;
    }

    static void Main()
    {
        int N = 5, K = 6;
        List<int> arr = new List<int> { 1, 1, 1, 1, 1 };
        Console.WriteLine(Solve(N, K, arr));
        Console.ReadLine();
    }
}

function solve(N, K, arr) {
    // Array to store the pair of {minimum cost to reach
    // the point either from point 0 or from point (N + 1),
    // cost to reach the index from point 0}
    let cost = [];
    for (let i = 0; i < N; i++) {
        cost.push(
            { min: Math.min(arr[i] + i + 1, arr[i] + N - i),
            cost: arr[i] + i + 1 });
    }

    // Sort the cost according to the min cost to reach the
    // point either from point 0 or from point (N + 1)
    cost.sort((a, b) => a.min - b.min);

    // Array to store the prefix sum of the total cost to
    // jump from i points having the smallest cost
    let prefSum = [0];

    for (let i = 0; i < N; i++) {
        prefSum.push(prefSum[i] + cost[i].min);
    }

    // Variable to store the maximum jumps across all the
    // starting points
    let ans = 0;

    for (let i = 0; i < N; i++) {
        // Assume that we start with ith point, so we reach
        // ith point from point 0

        // Remaining cost after choosing the ith point as
        // the starting point
        let remainingCost = K - cost[i].cost;

        // Initializing the range of jumps
        let low = 0, high = N;

        // Variable to store the maximum jumps with ith
        // point being the starting point
        let maxJumps = 0;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            let price = prefSum[mid];
            let currJumps = mid + 1;

            // If the starting point is in the current
            // range, then remove the extra cost of the
            // starting point
            if (mid > i) {
                price -= cost[i].min;
                currJumps -= 1;
            }

            // If the current price is less than or equal to
            // the remaining cost, then it means we can have
            // mid number of jumps
            if (price <= remainingCost) {
                maxJumps = Math.max(maxJumps, currJumps);
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
        ans = Math.max(ans, maxJumps);
    }
    return ans;
}

let N = 5, K = 6;
let arr = [1, 1, 1, 1, 1];
console.log(solve(N, K, arr));

2

Time Complexity: O(N * log N) where N is the number of integer points on the number line.
Auxiliary Space: O(N)