Distance covered after last breakpoint with at most K cost

Given an array arr[] of size Nand integers K and Dconsisting of breakpoints in the journey, the task is to find the distance covered after the last breakpoint with at most K cost following the given conditions:

  • Starting point is 0
  • 1 unit distance is covered for 1 cost.
  • For moving D continuous distance there is an extra cost of D ie, total cost becomes D*1 + D = 2D.

Note: If N = 0 that means there is no breakpoint and starting is from 0.

Examples:

Input: arr[] = {17, 12, 18}, K = 28, D = 8
Output: 2
Explanation: Movement from 0 to 8. Covered distance cost = 8*1 + 8 = 16
Movement from 8 to 12 as 12 is a break point. Cost = 12 – 8 = 4. Total cost = 16 + 4 = 20.
Movement from 12 to 17. Cost = 17 – 12 = 5. Total cost = 20 + 5 = 25.
Movement from 17 to 18. Cost = 18 – 17 = 1. Total Cost = 26.
Remaining cost = 2.
So extra distance that can be covered after last breakpoint(18) = 2.

Input: arr[] = {}, K = 100, D = 8
Output: 52
Explanation: Movement from 0 to 8. Distance = 8. Cost = 8*1 + 8 = 16. Total = 16
Movement from 8 to 16. Distance = 8. Cost = 8*1 + 8 = 16. Total = 32.
Movement from 16 to 24. Distance = 8. Cost = 8*1 + 8 = 16. Total = 48.
Movement from 24 to 32. Distance = 8. Cost = 8*1 + 8 = 16. Total = 64.
Movement from 32 to 40. Distance = 8. Cost = 8*1 + 8 = 16. Total = 80.
Movement from 40 to 48. Distance = 8. Cost = 8*1 + 8 = 16. Total = 96.
Movement from 48 to 52. Distance = 4. Cost = 4*1 = 4. Total = 100.
Distance covered after last breakpoint (no breakpoint here) = 52.

Approach: The given problem can be solved based on the following mathematical observation:

Distance between two consecutive breakpoints X and Y is (X – Y).
The number of times D consecutive movements are made = floor((X – Y)/D).
The cost for these consecutive movements is 2*D * floor((XY)/D).
Say M cost is paid to reach the last breakpoint.
Then the extra D consecutive distances that can be covered is floor((K – M)/2*D).
The cost for this is D* floor((K – M)/2*D). If the remaining cost is > D then only D additional distance can be covered.

Follow the steps to solve the problem:

  • First check for Edge Case N = 0
  • If N!=0 then sort the given breakpoints.
  • Calculate the distance from the 1st point to 0th point.
  • Traverse the array from i = 1 to N – 1.
    • Calculate the distance between arr[i] and arr[i-1].
    • Calculate the cost to cover this distance (say Count).
  • If, K<= Countreturn 0
  • Calculate the extra distance by using the above observation:
    • Res = D*(( K – Count) / (2*D) ) (number of times continuous D distances covered)
    • Rem = (K – Count) % (2*D) (Remaining cost)
    • If, Rem >= D && Rem <=(2*D-1) then Rem = D
  • return, Res + Rem as the final extra distance covered.

Below is the implementation of the above approach:

C++

 

#include <bits/stdc++.h>

using namespace std;

 

int countDays(int* arr, int N, int K, int D)

{

    

    if (N == 0) {

        int Res = D * (K / (2 * D));

        int Rem = K % (2 * D);

        if (Rem >= D && Rem <= (2 * D - 1))

            Rem = D;

        return (Res + Rem);

    }

 

    

    sort(arr, arr + N);

 

    

    

    int Count = 2 * D * (arr[0] / D)

                + arr[0] % D;

    int Curr = 0;

 

    

    for (int i = 1; i < N; i++) {

 

        

        

        if ((arr[i] - arr[i - 1]) >= 1) {

 

            

            

            Curr = arr[i] - arr[i - 1];

 

            

            Count += 2 * D * (Curr / D)

                     + (Curr % D);

        }

    }

 

    

    if (K <= Count)

        return 0;

 

    

    int Res = D * ((K - Count) / (2 * D));

    int Rem = (K - Count) % (2 * D);

 

    

    if (Rem >= D && Rem <= (2 * D - 1))

        Rem = D;

 

    

    return (Res + Rem);

}

 

int main()

{

    int arr[] = { 17, 12, 18 };

    int D = 8;

    int N = sizeof(arr) / sizeof(arr[0]);

    int K = 28;

 

    

    cout << countDays(arr, N, K, D);

    return 0;

}

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

Leave a Comment