Dado N, imprima la secuencia de un número mínimo de pasos en los que N se puede obtener a partir de 0 mediante la suma o resta del número de paso.
Nota : en cada paso, podemos sumar o restar un número igual al número de paso de la posición actual. Por ejemplo, en el paso 1 podemos sumar 1 o -1. De manera similar, en el paso 2 sumamos 2 o -2 y así sucesivamente.
El siguiente diagrama muestra todas las posiciones posibles que se pueden alcanzar desde 0 en 3 pasos realizando las operaciones especificadas.
Ejemplos:
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
Enfoque: El enfoque para resolver el problema anterior es marcar los números de paso donde tenemos que restar o sumar si N es positivo o negativo respectivamente. Si N es positivo, agregue números en cada paso, hasta que la suma exceda N. Una vez que la suma exceda N, verifique si suma-N es par o no. Si sum-N es par, entonces en el paso número (sum-N)/2, se debe realizar la resta. Si sum-N es un número impar, compruebe si el último paso en el que sum excedió a N fue par o impar. Si fue impar, realice un paso más, de lo contrario, realice dos pasos. Si suma = N en cualquier paso, entonces la suma o resta en cada paso dará la respuesta.
Sea N = 11, entonces 1+2+3+4+5=15 excede 11. Resta 15-11 para obtener 4, lo que equivale a realizar la resta en el paso 2. Por lo tanto, la secuencia de pasos es 1 -2 3 4 5
Sea N=12, entonces 1+2+3+4+5=15 excede 11. Resta 15-12 para obtener 3, que no se puede realizar en ningún paso. Así que agregue dos pasos más, uno es el paso 6 y el paso 7 . El objetivo es hacer que la suma-N sea par, así que realice la suma en el paso 6 y la resta en el paso 7, que se combinan para restar 1 de la suma. Ahora suma-N es par, 14-12=2 que es equivalente a realizar la resta en el paso 1. Por lo tanto, la secuencia de pasos es -1 2 3 4 5 6 -7
Sea N=20, luego 1+2+3+4+5+6 excede 20. Resta 21-20 para obtener 1, así que suma 7 a 21 para obtener 28. Realizar la suma en el siguiente paso será como (suma-n) es impar. suma-N da 8, que es equivalente a realizar la resta en el paso 4. Por lo tanto, la secuencia de pasos es 1 2 3 -4 5 6 7.
A continuación se muestra la ilustración del enfoque anterior:
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 sequence vector<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 steps void 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 Code int 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 sequence static 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 steps static 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 Code public 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 sequence static 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 steps static 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 Code public 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 sequence function 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 steps function 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 Code var 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 sequence def 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 steps def 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 Code if __name__ == '__main__': n = 20 prSteps(n)
7 Minimum number of Steps: 7 Step sequence:1 2 3 -4 5 6 7
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(sqrt(N))
Nota: sum = i*(i+1)/2 es equivalente o mayor que N, lo que da i como sqrt(N).
Publicación traducida automáticamente
Artículo escrito por Shreyans Vora y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA