Given N, print the sequence of a minimum number of steps in which N can be obtained starting from 0 using addition or subtraction of the step number.
Note: At each step, we can add or subtract a number equal to the step number from the current position. For example, at step 1 we can add 1 or -1. Similarly, at step 2 we add 2 or -2 and so on.
The below diagram shows all possible positions that can be reached from 0 in 3 steps by performing the specified operations.
Examples :
Input: n = -4
Output: Minimum number of Steps: 3
Step sequence: 1 -2 -3
Explanation:
Step 1: At step 1 we add 1 to move from 0 to 1.
Step 2: At step 2 we add (-2) to move from 1 to -1.
Step 3: At step 3 we add (-3) to move from -1 to -4.
Input: n = 11
Output: Minimum number of steps = 4
Step sequence: 1 -2 3 4 5
Approach: The approach to solve the above problem is to mark the step numbers where we have to subtract or add where if N is positive or negative respectively. If N is positive, add numbers at every step, until the sum exceeds N. Once the sum exceeds N, check if sum-N is even or not. If sum-N is even, then at step number (sum-N)/2, subtraction is to be done. If sum-N is an odd number, then check if the last step at which sum exceeded N was even or odd. If it was odd, perform one more step else perform two steps. If sum = N at any step, then addition or subtraction at every step will give the answer.
Let N = 11, then 1+2+3+4+5=15 exceeds 11. Subtract 15-11 to get 4, which is equivalent to performing subtraction at step 2. Hence the sequence of steps is 1 -2 3 4 5
Let N=12, then 1+2+3+4+5=15 exceeds 11. Subtract 15-12 to get 3, which cannot be performed at any step. So add two more steps, one is the 6th step and 7th step. The target is to make sum-N even, so perform addition at 6th step and subtraction at 7th step, which combines to subtract 1 from the sum. Now sum-N is even, 14-12=2 which is equivalent to performing subtraction at step 1. Hence the sequence of steps are -1 2 3 4 5 6 -7
Let N=20, then 1+2+3+4+5+6 exceeds 20. Subtract 21-20 to get 1, so add 7 to 21 to get 28. Performing addition at next step will do as (sum-n) is odd. sum-N gives 8 which is equivalent to performing subtraction at step 4. Hence the sequence of steps is 1 2 3 -4 5 6 7.
Below is the illustration of the above approach:
C++
// C++ program to print the sequence// of minimum steps in which N can be// obtained from 0 using addition or// subtraction of the step number.#include <bits/stdc++.h>using namespace std;// Function to return the vector// which stores the step sequencevector<int> findSteps(int n){ // Steps sequence vector<int> ans; // Current sum int sum = 0; // Sign of the number int sign = (n >= 0 ? 1 : -1); n = abs(n); int i; // Basic steps required to get sum >= required value. for (i = 1; sum < n; i++) { ans.push_back(sign * i); sum += i; } cout << i << endl; // Reached ahead of N if (sum > sign * n) { // If the last step was an odd number if (i % 2) { sum -= n; // sum-n is odd if (sum % 2) { ans.push_back(sign * i); sum += i++; } // subtract the equivalent sum-n ans[(sum / 2) - 1] *= -1; } else { sum -= n; // sum-n is odd if (sum % 2) { // since addition of next step and subtraction // at the next step will give sum = sum-1 sum--; ans.push_back(sign * i); ans.push_back(sign * -1 * (i + 1)); } // subtract the equivalent sum-n ans[(sum / 2) - 1] *= -1; } } // returns the vector return ans;}// Function to print the stepsvoid printSteps(int n){ vector<int> v = findSteps(n); // prints the number of steps which is the size of vector cout << "Minimum number of Steps: " << v.size() << "\n"; cout << "Step sequence:"; // prints the steps stored // in the vector for (int i = 0; i < v.size(); i++) cout << v[i] << " ";}// Driver Codeint main(){ int n = 20; printSteps(n); return 0;} |
Java
// Java program to print the // sequence of minimum steps // in which N can be obtained // from 0 using addition or // subtraction of the step // number.import java.util.*;class GFG{// Function to return the// Arraylist which stores // the step sequencestatic ArrayList<Integer> findSteps(int n){ // Steps sequence ArrayList<Integer> ans = new ArrayList<Integer>(); // Current sum int sum = 0; // Sign of the number int sign = (n >= 0 ? 1 : -1); n = Math.abs(n); int i; // Basic steps required to // get sum >= required value. for (i = 1; sum < n; i++) { ans.add(sign * i); sum += i; } System.out.println( i ); // Reached ahead of N if (sum > sign * n) { // If the last step // was an odd number if (i % 2 != 0) { sum -= n; // sum-n is odd if (sum % 2 != 0) { ans.add(sign * i); sum += i++; } // subtract the // equivalent sum-n ans.set((sum / 2) - 1, ans.get((sum / 2) - 1) * -1); } else { sum -= n; // sum-n is odd if (sum % 2 != 0) { // since addition of next // step and subtraction at // the next step will // give sum = sum-1 sum--; ans.add(sign * i); ans.add(sign * -1 * (i + 1)); } // subtract the // equivalent sum-n ans.set((sum / 2) - 1, ans.get((sum / 2) - 1) * -1); } } // returns the Arraylist return ans;}// Function to print the stepsstatic void printSteps(int n){ ArrayList<Integer> v = findSteps(n); // prints the number of steps // which is the size of Arraylist System.out.println("Minimum number " + "of Steps: " + v.size()); System.out.print("Step sequence:"); // prints the steps stored // in the Arraylist for (int i = 0; i < v.size(); i++) System.out.print(v.get(i) + " ");}// Driver Codepublic static void main(String args[]){ int n = 20; printSteps(n);}}// This code is contributed// by Arnab Kundu |
C#
// C# program to print the // sequence of minimum steps // in which N can be obtained // from 0 using addition or // subtraction of the step // number.using System;using System.Collections.Generic;class GFG{// Function to return the// Arraylist which stores // the step sequencestatic List<int> findSteps(int n){ // Steps sequence List<int> ans = new List<int>(); // Current sum int sum = 0; // Sign of the number int sign = (n >= 0 ? 1 : -1); n = Math.Abs(n); int i; // Basic steps required to // get sum >= required value. for (i = 1; sum < n; i++) { ans.Add(sign * i); sum += i; } Console.WriteLine( i ); // Reached ahead of N if (sum > sign * n) { // If the last step // was an odd number if (i % 2 != 0) { sum -= n; // sum-n is odd if (sum % 2 != 0) { ans.Add(sign * i); sum += i++; } // subtract the // equivalent sum-n ans[(sum / 2) - 1]= ans[(sum / 2) - 1] * -1; } else { sum -= n; // sum-n is odd if (sum % 2 != 0) { // since addition of next // step and subtraction at // the next step will // give sum = sum-1 sum--; ans.Add(sign * i); ans.Add(sign * -1 * (i + 1)); } // subtract the // equivalent sum-n ans[(sum / 2) - 1]= ans[(sum / 2) - 1] * -1; } } // returns the Arraylist return ans;}// Function to print the stepsstatic void printSteps(int n){ List<int> v = findSteps(n); // prints the number of steps // which is the size of Arraylist Console.WriteLine("Minimum number " + "of Steps: " + v.Count); Console.Write("Step sequence:"); // prints the steps stored // in the Arraylist for (int i = 0; i < v.Count; i++) Console.Write(v[i] + " ");}// Driver Codepublic static void Main(String []args){ int n = 20; printSteps(n);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to print the sequence// of minimum steps in which N can be// obtained from 0 using addition or// subtraction of the step number.// Function to return the vector// which stores the step sequencefunction findSteps(n){ // Steps sequence var ans = []; // Current sum var sum = 0; // Sign of the number var sign = (n >= 0 ? 1 : -1); n = Math.abs(n); var i; // Basic steps required to get sum >= required value. for (i = 1; sum < n; i++) { ans.push(sign * i); sum += i; } document.write( i + "<br>"); // Reached ahead of N if (sum > sign * n) { // If the last step was an odd number if (i % 2) { sum -= n; // sum-n is odd if (sum % 2) { ans.push(sign * i); sum += i++; } // subtract the equivalent sum-n ans[(sum / 2) - 1] *= -1; } else { sum -= n; // sum-n is odd if (sum % 2) { // since addition of next step and subtraction // at the next step will give sum = sum-1 sum--; ans.push(sign * i); ans.push(sign * -1 * (i + 1)); } // subtract the equivalent sum-n ans[(sum / 2) - 1] *= -1; } } // returns the vector return ans;}// Function to print the stepsfunction printSteps(n){ var v = findSteps(n); // prints the number of steps which is the size of vector document.write( "Minimum number of Steps: " + v.length + "<br>"); document.write( "Step sequence:"); // prints the steps stored // in the vector for (var i = 0; i < v.length; i++) document.write( v[i] + " ");}// Driver Codevar n = 20;printSteps(n);// This code is contributed by itsok.</script> |
Python3
# Python3 program to print the sequence# of minimum steps in which N can be# obtained from 0 using addition or# subtraction of the step number.# Function to return the # which stores the step sequencedef findSteps( n): # Steps sequence ans=[] # Current sum sum = 0 # Sign of the number sign = 1 if n >= 0 else -1 n = abs(n) i=1 # Basic steps required to get sum >= required value. while sum<n : ans.append(sign * i) sum += i i+=1 print(i) # Reached ahead of N if (sum > sign * n) : # If the last step was an odd number if (i % 2) : sum -= n # sum-n is odd if (sum % 2) : ans.append(sign * i) sum += i i+=1 # subtract the equivalent sum-n ans[int((sum / 2) - 1)] *= -1 else : sum -= n # sum-n is odd if (sum % 2) : # since addition of next step and subtraction # at the next step will give sum = sum-1 sum-=1 ans.append(sign * i) ans.append(sign * -1 * (i + 1)) # subtract the equivalent sum-n ans[int((sum / 2) - 1)] *= -1 # returns the return ans# Function to pr the stepsdef prSteps(n): v = findSteps(n) # print the number of steps which is the size of print("Minimum number of Steps:",len(v)) print("Step sequence:",end="") # print the steps stored # in the for i in range(len(v)): print(v[i],end=" ")# Driver Codeif __name__ == '__main__': n = 20 prSteps(n) |
7 Minimum number of Steps: 7 Step sequence:1 2 3 -4 5 6 7
Time Complexity : O(sqrt(N))
Auxiliary Space : O(sqrt(N))
Note: sum = i*(i+1)/2 is equivalent or greater than N, which gives i as sqrt(N).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!