Given an integer N, the task is to find the minimum steps to visit all integers in the range [1, N] by selecting any integer and jump i steps at every ith jump.
Note: It is possible to revisit an integer more than once.
Examples:
Input: N = 6
Output: 3
Explanation:
One of the following way is:
First start at first number and visit the integers {1, 2, 4}.
Now start at 2nd number and visit the integers as {2, 3, 5}
Now start at the last number and visit it.
Therefore, in total of 3 steps one can visit all the numbers in the range [1, 6]. And also it is the minimum number of steps needed.Input: N = 4
Output: 2
Naive Approach: The given problem can be solved based on the following observations:
- In each step the sizes of jumps increases therefore some numbers remains unvisited in a step.
- Starting from the first number and performing the jumps it can be observed that the maximum size of the jump is the total number of steps needed to visit every number. As in one move, one cannot visit each number between two unvisited numbers.
Follow the below steps to solve the problem:
- Initialize two variables, say count = 1 and res = 0.
- Traverse over the range [1, N] and increment i by count and update res as res =max(res, count) and increment count by 1.
- After completing the above steps print the res.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Utility function to find minimum steps int minSteps( int N) { // Initialize count and result int count = 1, res = 0; // Traverse over the range [1, N] for ( int i = 1; i <= N; i += count) { // Update res res = max(res, count); // Increment count count++; } // Return res return res; } // Driver Code int main() { // Input int N = 6; // Function call cout << minSteps(N) << "\n" ; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Utility function to find minimum steps static int minSteps( int N) { // Initialize count and result int count = 1 , res = 0 ; // Traverse over the range [1, N] for ( int i = 1 ; i <= N; i += count) { // Update res res = Math.max(res, count); // Increment count count++; } // Return res return res; } // Driver Code public static void main (String[] args) { // Input int N = 6 ; // Function call System.out.println(minSteps(N) ); } } // This code is contributed by Potta Lokesh |
Python3
# Python 3 implementation of the above approach # Utility function to find minimum steps def minSteps(N): # Initialize count and result count = 1 res = 0 # Traverse over the range [1, N] for i in range ( 1 , N + 1 , count): # Update res res = max (res, count) # Increment count count + = 1 # Return res return res # Driver Code if __name__ = = '__main__' : # Input N = 6 # Function call print (minSteps(N)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG{ // Utility function to find minimum steps static int minSteps( int N) { // Initialize count and result int count = 1, res = 0; // Traverse over the range [1, N] for ( int i = 1; i <= N; i += count) { // Update res res = Math.Max(res, count); // Increment count count++; } // Return res return res; } // Driver Code public static void Main() { // Input int N = 6; // Function call Console.Write(minSteps(N) ); } } |
Javascript
<script> // JavaScript implementation of the above approach // Utility function to find minimum steps function minSteps(N) { // Initialize count and result let count = 1, res = 0; // Traverse over the range [1, N] for (let i = 1; i <= N; i += count) { // Update res res = Math.max(res, count); // Increment count count++; } // Return res return res; } // Driver Code // Input let N = 6; // Function call document.write(minSteps(N)); </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The above steps can be optimized based on the following observations:
- Suppose an array arr[] as arr[] ={1, 1, 2, 2, 2, 3, 3, 3, ….]. Now the idea is to find the number K which is the maximum size of jump taken in a step.
- In above taken array, Since, 1 occurs twice, 2 occurs thrice, 3 occurs four times and so on. (K – 1) would occur K times.
- Now let K occurs c times, then count of total occurrence must be equal to N.
- 2 + 3 + 4 +….+ K + c = N
- c = N – 2 – 3 – 4 -….- K …..(i)
- Then one need to find the greatest K satisfying equation (i) also c?1, then
- K2 + K – 2 × N ? 0.
- Therefore, K = (-1 + ?(1 + 8 ×N)) / 2
Follow the steps below to solve the problem:
- Print the value (-1 + ?(1 + 8 *N)) / 2.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Utility function to find minimum steps int minSteps( int N) { int res = ( sqrt (1 + 8 * N) - 1) / 2; return res; } // Driver code int main() { // Input integer int N = 6; // Function call cout << minSteps(N) << "\n" ; } |
Java
// Java implementation of the above approach import java.io.*; import java.lang.Math; class GFG{ // Utility function to find minimum steps static int minSteps( int N) { int res = (( int )Math.sqrt( 1 + 8 * N) - 1 ) / 2 ; return res; } // Driver code public static void main (String[] args) { // Input integer int N = 6 ; // Function call System.out.println(minSteps(N) + "\n" ); } } // This code is contributed by shivanisinghss2110 |
Python3
# Python 3 implementation of the above approach from math import sqrt # Utility function to find minimum steps def minSteps(N): res = int ((sqrt( 1 + 8 * N) - 1 ) / / 2 ) return res # Driver code if __name__ = = '__main__' : # Input integer N = 6 # Function call print (minSteps(N)) |
C#
// Java implementation of the above approach using System; class GFG { // Utility function to find minimum steps static int minSteps( int N) { int res = (( int )Math.Sqrt(1 + 8 * N) - 1) / 2; return res; } // Driver code public static void Main (String[] args) { // Input integer int N = 6; // Function call Console.Write(minSteps(N) + "\n" ); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // javascript implementation of the above approach // Utility function to find minimum steps function minSteps(N) { var res = parseInt((Math.sqrt(1 + 8 * N) - 1) / 2); return res; } // Driver code // Input integer var N = 6; // Function call document.write(minSteps(N)); // This code contributed by shikhasingrajput </script> |
3
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!