Minimize jumps to reach X by jumping K positions or 1 position

View Discussion

Improve Article

Save Article

Like Article

Given two values X and K, the task is to minimize the number of jumps to reach X from 0 by jumping K positions or 1 position at a time.

Example: 

Input: N = 5, K = 2
Output: 3
Explanation: First two jumps of K = 2 steps and 
third jump of 1 step will be required

Input: N = 3, K = 5
Output: 3
Explanation: First two jumps of 1 step will be required 
and the third jump will be of 3 positions. Or
Use two jumps of 3 spositions to reach 6 and 
then jump 1 position on left to reach 5
 

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

To minimize the steps, it is optimal to cover as much distance as possible using jumps of K positions. Say N and M are the two multiples of K that are closest to X (N ≤ X and M > X).

So steps required to reach X can be:

  • S1 = N/K + (X – N)
  • S2 = M/K + (M – X)

The minimum number of steps = minimum between S1 and S2

Follow the steps mentioned below to solve the problem:

  • Get the values S1 and S2.
  • Find the minimum between them.
  • Return the minimum value as the answer.

Below is the implementation for the above approach: 

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int findJumps(int X, int K)

{

    

    int div1 = X / K;

    int div2 = X / K + 1;

  

    int N = div1 * K, M = div2 * K;

  

    

    int S1 = div1 + (X - N);

    int S2 = div2 + (M - X);

  

    

    return min(S1, S2);

}

  

int main()

{

    int X = 5, K = 2;

  

    

    cout << findJumps(X, K);

    return 0;

}

Time Complexity: O(1)
Auxiliary Space: O(1)

By Julio MarchiPosted on