Given two integers N and K where K represents the number of jumps that we are allowed to make directly from N reducing N to N – K, our task is to count minimum steps to reach 0 following the given operations:
- We can jump by a amount of K from N that is N = N – K
- Decrement N by 1 that is N = N -1.
Examples:
Input: N = 11, K = 4
Output: 5
Explanation:
For the given value N we can perform the operation in the given sequence: 11 -> 7 -> 3 -> 2 -> 1 -> 0Input: N = 6, K = 3
Output: 2
Explanation:
For the given value N we can perform the operation in the given sequence: 6 -> 3 -> 0.
Approach:
To solve the problem mentioned above we know that it will take N / K steps to directly jump from value N to least divisible value with K and N % K steps to decrement it by 1 such as to reduce the count to 0. So the total number of steps required to reach 0 from N will be
(N / K) + (N % K)
Below is the implementation of the above approach:
C++
// C++ program to Count the minimum steps// to reach 0 from the given integer N#include <bits/stdc++.h>using namespace std;// Function returns min step// to reach 0 from Nint getMinSteps(int n, int jump){ // Direct possible // reduction of value N int quotient = n / jump; // Remaining steps needs // to be reduced by 1 int remainder = n % jump; // Summation of both the values int steps = quotient + remainder; // Return the final answer return steps;}// Driver codeint main(){ int N = 6, K = 3; cout << getMinSteps(N, K); return 0;} |
Java
// Java program to count the minimum steps// to reach 0 from the given integer Nclass GFG{// Function returns min step// to reach 0 from Nstatic int getMinSteps(int n, int jump){ // Direct possible // reduction of value N int quotient = n / jump; // Remaining steps needs // to be reduced by 1 int remainder = n % jump; // Summation of both the values int steps = quotient + remainder; // Return the final answer return steps;}// Driver codepublic static void main(String[] args){ int N = 6, K = 3; System.out.print(getMinSteps(N, K));}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program to Count the minimum steps # to reach 0 from the given integer N # Function returns min step # to reach 0 from N def getMinSteps(n, jump): # Direct possible # reduction of value N quotient = int(n / jump) # Remaining steps needs # to be reduced by 1 remainder = n % jump # Summation of both the values steps = quotient + remainder # Return the final answer return steps# Driver code N = 6K = 3print (getMinSteps(N, K))# This code is contributed by PratikBasu |
C#
// C# program to count the minimum steps // to reach 0 from the given integer N using System;class GFG{ // Function returns min step // to reach 0 from N static int getMinSteps(int n, int jump) { // Direct possible // reduction of value N int quotient = n / jump; // Remaining steps needs // to be reduced by 1 int remainder = n % jump; // Summation of both the values int steps = quotient + remainder; // Return the final answer return steps; } // Driver code public static void Main(string[] args) { int N = 6, K = 3; Console.Write(getMinSteps(N, K)); } } // This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript program to Count the minimum steps// to reach 0 from the given integer N// Function returns min step// to reach 0 from Nfunction getMinSteps(n, jump){ // Direct possible // reduction of value N let quotient = Math.floor(n / jump); // Remaining steps needs // to be reduced by 1 let remainder = n % jump; // Summation of both the values let steps = quotient + remainder; // Return the final answer return steps;}// Driver code let N = 6, K = 3; document.write(getMinSteps(N, K));// This code is contributed by Surbhi Tyagi.</script> |
2
Time Complexity: O(1).
We are using constant time to compute the minimum steps to reach 0 from N.
Space Complexity: O(1).
We are not using any extra space for computing the steps.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!