Given an infinite number line from the range [-INFINITY, +INFINITY] and an integer N, the task is to find the minimum count of moves required to reach the N, starting from 0, by either moving i steps forward or 1 steps backward in every ith move.
Examples:
Input: N = 18
Output: 6
Explanation:
To reach to the given value of N, perform the operations in the following sequence: 1 – 1 + 3 + 4 + 5 + 6 = 18
Therefore, a total of 6 operations are required.Input: N = 3
Output: 2
Explanation:
To reach to the given value of N, perform the operations in the following sequence: 1 + 2 = 3
Therefore, a total of 2 operations are required.
Approach: The idea is to initially, keep adding 1, 2, 3 . . . . K, until it is greater than or equal to the required value N. Then, calculate the required number to be subtracted from the current sum. Follow the steps below to solve the problem:
- Initially, increment by K until N is greater than the current value. Now, stop at some position
pos = 1 + 2 + …………. + steps = steps ? (steps + 1) / 2 ? N.
Note: 0 ? pos – N < steps. Otherwise, the last step wasn’t possible.- Case 1: If pos = N then, ‘steps’ is the required answer.
- Case 2: If pos ? N, then replace any iteration of K with -1.
- By replacing any K with -1, the modified value of pos = pos – (K + 1). Since K ? [1, steps], then pos ? [pos – steps – 1, pos – 2].
- It is clear that pos – step < N. If N < pos – 1, then choose the corresponding K = pos – N – 1 and replace K with -1 and get straight to the point N.
- If N + 1 = pos, only one -1 operation is required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum steps// required to reach N by either moving// i steps forward or 1 steps backwardint minimumsteps(int N){ // Stores the required count int steps = 0; // IF total moves required // is less than double of N while (steps * (steps + 1) < 2 * N) { // Update steps steps++; } // Steps required to reach N if (steps * (steps + 1) / 2 == N + 1) { // Update steps steps++; } cout << steps;}// Driver Codeint main(){ // Given value of N int N = 18; minimumsteps(N);} |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function to find the minimum steps// required to reach N by either moving// i steps forward or 1 steps backwardstatic void minimumsteps(int N){ // Stores the required count int steps = 0; // IF total moves required // is less than double of N while (steps * (steps + 1) < 2 * N) { // Update steps steps++; } // Steps required to reach N if (steps * (steps + 1) / 2 == N + 1) { // Update steps steps++; } System.out.println(steps);} // Driver codepublic static void main(String[] args){ // Given value of N int N = 18; minimumsteps(N);}}// This code is contributed by code_hunt. |
Python3
# Function to find the minimum steps# required to reach N by either moving# i steps forward or 1 steps backwarddef minimumsteps(N) : # Stores the required count steps = 0 # IF total moves required # is less than double of N while (steps * (steps + 1) < 2 * N) : # Update steps steps += 1 # Steps required to reach N if (steps * (steps + 1) / 2 == N + 1) : # Update steps steps += 1 print(steps)# Driver codeN = 18;minimumsteps(N)# This code is contributed by Dharanendra L V |
C#
// C# program for the above approach using System;class GFG { // Function to find the minimum steps // required to reach N by either moving // i steps forward or 1 steps backward static void minimumsteps(int N) { // Stores the required count int steps = 0; // IF total moves required // is less than double of N while (steps * (steps + 1) < 2 * N) { // Update steps steps++; } // Steps required to reach N if (steps * (steps + 1) / 2 == N + 1) { // Update steps steps++; } Console.WriteLine(steps); } // Driver code static public void Main() { // Given value of N int N = 18; minimumsteps(N); }}// This code is contributed by Dharanendra LV |
Javascript
<script>// JavaScript program for the above approach// Function to find the minimum steps// required to reach N by either moving// i steps forward or 1 steps backwardfunction minimumsteps(N){ // Stores the required count let steps = 0; // IF total moves required // is less than double of N while (steps * (steps + 1) < 2 * N) { // Update steps steps++; } // Steps required to reach N if (steps * Math.floor((steps + 1) / 2) == N + 1) { // Update steps steps++; } document.write(steps);}// Driver Code// Given value of Nlet N = 18;minimumsteps(N);// This code is contributed by Surbhi Tyagi.</script> |
Output:
6
Time CompleNity: O(sqrt(N))
AuNiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
