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