Agregar uno al número representado como una array de dígitos

Dado un número no negativo representado como una array de dígitos, agregue 1 al número (incremente el número representado por los dígitos). Los dígitos se almacenan de manera que el dígito más significativo sea el primer elemento de la array.

Ejemplos: 

Input : [1, 2, 4]
Output : [1, 2, 5]

Input : [9, 9, 9]
Output : [1, 0, 0, 0]

Enfoque: Para agregar uno al número representado por dígitos, siga los pasos a continuación: 

• Analice la array dada desde el final como lo hacemos en la suma escolar.
• Si los últimos elementos son 9, hazlo 0 y lleva = 1.
• Para la siguiente iteración, verifique llevar y si suma 10, haga lo mismo que en el paso 2.
• Después de agregar carry, haga carry = 0 para la siguiente iteración.
• Si los vectores se suman y aumentan el tamaño del vector, agregue 1 al principio.

A continuación se muestra la implementación para sumar 1 al número representado por dígitos. 

// CPP implementation for Adding one
// to number represented by digits
#include <bits/stdc++.h>
using namespace std;
 
// function for adding one to number
void incrementVector(vector<int>& a)
{
    int n = a.size();
 
    // Add 1 to last digit and find carry
    a[n - 1] += 1;
    int carry = a[n - 1] / 10;
    a[n - 1] = a[n - 1] % 10;
 
    // Traverse from second last digit
    for (int i = n - 2; i >= 0; i--) {
        if (carry == 1) {
            a[i] += 1;
            carry = a[i] / 10;
            a[i] = a[i] % 10;
        }
    }
 
    // If carry is 1, we need to add
    // a 1 at the beginning of vector
    if (carry == 1)
        a.insert(a.begin(), 1);
}
 
// driver code
int main()
{
    vector<int> vect{ 1, 7, 8, 9 };
 
    incrementVector(vect);
 
    for (int i = 0; i < vect.size(); i++)
        cout << vect[i] << " ";
 
    return 0;
}

// Java implementation for Adding one
// to number represented by digits
import java.io.*;
import java.util.*;
 
class GFG {
 
    // function for adding one to number
    static void incrementVector(Vector<Integer> a)
    {
        int n = a.size();
 
        // Add 1 to last digit and find carry
        a.set(n - 1, a.get(n - 1) + 1);
        int carry = a.get(n - 1) / 10;
        a.set(n - 1, a.get(n - 1) % 10);
 
        // Traverse from second last digit
        for (int i = n - 2; i >= 0; i--) {
            if (carry == 1) {
                a.set(i, a.get(i) + 1);
                carry = a.get(i) / 10;
                a.set(i, a.get(i) % 10);
            }
        }
 
        // If carry is 1, we need to add
        // a 1 at the beginning of vector
        if (carry == 1)
            a.add(0, 1);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        Vector<Integer> vect = new Vector<Integer>();
        vect.add(1);
        vect.add(7);
        vect.add(8);
        vect.add(9);
 
        incrementVector(vect);
 
        for (int i = 0; i < vect.size(); i++)
            System.out.print(vect.get(i) + " ");
    }
}
 
// This code is contributed by Gitanjali.

// C# implementation for Adding one
// to number represented by digits
using System;
using System.Xml;
 
namespace myTry {
class Program {
    // Driver code
    static void Main(string[] args)
    {
        int carry = 0;
        int[] array = new int[] { 1, 7, 8, 9 };
 
        // find the length of the array
        int n = array.Length;
 
        // Add 1 to the last digit and find carry
        array[n - 1] += 1;
        carry = array[n - 1] / 10;
        array[n - 1] = array[n - 1] % 10;
 
        // Traverse from second last digit
        for (int i = n - 2; i >= 0; i--) {
            if (carry == 1) {
                array[i] += 1;
                carry = array[i] / 10;
                array[i] = array[i] % 10;
            }
        }
 
        // If the carry is 1, we need to add
        // a 1 at the beginning of the array
        if (carry == 1) {
            Array.Resize(ref array, n + 1);
            array[0] = carry;
        }
 
        for (int i = 0; i < array.Length; i++)
            Console.WriteLine(array[i] + " ");
    }
}
}

# Python implementation for Adding one
# to number represented by digits
 
import math
 
# function for adding one to number
 
 
def incrementVector(a):
 
    n = len(a)
 
    # Add 1 to last digit and find carry
    a[n-1] += 1
    carry = a[n-1]/10
    a[n-1] = a[n-1] % 10
 
    # Traverse from second last digit
    for i in range(n-2, -1, -1):
        if (carry == 1):
            a[i] += 1
            carry = a[i]/10
            a[i] = a[i] % 10
 
    # If carry is 1, we need to add
    # a 1 at the beginning of vector
    if (carry == 1):
        a.insert(0, 1)
 
 
# driver code
vect = [1, 7, 8, 9]
 
incrementVector(vect)
 
for i in range(0, len(vect)):
    print(vect[i], end=" ")
 
# This code is contributed by Gitanjali.

<script>
// JavaScript implementation for Adding one
// to number represented by digits
 
// function for adding one to number
const incrementVector = (a) =>
{
let n = a.length;
 
// Add 1 to last digit and find carry
a[n - 1] += 1;
let carry = parseInt(a[n - 1] / 10);
a[n - 1] = a[n - 1] % 10;
 
// Traverse from second last digit
for (let i = n - 2; i >= 0; i--) {
    if (carry == 1) {
        a[i] += 1;
        carry = parseInt(a[i] / 10);
        a[i] = a[i] % 10;
    }
}
 
// If carry is 1, we need to add
// a 1 at the beginning of vector
if (carry == 1)
    a.unshift(1);
}
 
// driver code
 
let vect = [ 1, 7, 8, 9 ];
 
incrementVector(vect);
 
for (let i = 0; i < vect.length; i++)
    document.write(`${vect[i]} `);
 
// This code is contributed by rakeshsahni
 
</script>

1 7 9 0 

Complejidad de tiempo : O(n), donde n es el tamaño de la array.

Espacio Auxiliar : O(1)

Otro enfoque : comience desde el final del vector y si el último elemento es 9, configúrelo en 0, de lo contrario, salga del ciclo.

• Si el bucle establece todos los dígitos en 0 (si todos los dígitos fueran 9), inserte 1 al principio.
• De lo contrario, incremente el elemento en la posición donde se detuvo el bucle.
• No se necesita acarreo/división/módulo.

A continuación se muestra la implementación:

#include <iostream>
#include <vector>
 
using namespace std;
 
void AddOne(vector<int>& digits)
{
    // initialize an index (digit of units)
    int index = digits.size() - 1;
 
    // while the index is valid and the value at [index] ==
    // 9 set it as 0
    while (index >= 0 && digits[index] == 9)
        digits[index--] = 0;
 
    // if index < 0 (if all digits were 9)
    if (index < 0)
        // insert an one at the beginning of the vector
        digits.insert(digits.begin(), 1, 1);
 
    // else increment the value at [index]
    else
        digits[index]++;
}
 
// Driver code
int main()
{
    vector<int> digits{ 1, 7, 8, 9 };
 
    AddOne(digits);
 
    for (int digit : digits)
        cout << digit << ' ';
 
    return 0;
}
// This code is contributed
// by Gatea David

// Java implementation for Adding one
// to number represented by digits
import java.io.*;
import java.util.*;
class GFG {
 
  static void AddOne(Vector<Integer> digits)
  { 
 
    // initialize an index (digit of units)
    int index= digits.size() - 1;
 
    // while the index is valid and the value at [index] ==
    // 9 set it as 0
    while (index >= 0 && digits.get(index) == 9){
      digits.set(index, 0);
      index -= 1;
    }
 
    // if index < 0 (if all digits were 9)
    if (index < 0){
      // insert an one at the beginning of the vector
      digits.set(0, 1);
      //Add one extra zero at the end of the vector
      digits.add(digits.size(),0);
 
    }
       
    // else increment the value at [index]
    else
      digits.set(index, digits.get(index) + 1);
 
  }
 
  // Driver code
  public static void main(String[] args)
  {
    Vector<Integer> digits = new Vector<Integer>(Arrays.asList(1,7,8,9));
    AddOne(digits);
    for (int digit : digits)
      System.out.print(digit + " ");
  }
}
 
// This code is contributed by Shubham Singh

#Python Program
def AddOne(digits):
   
    # initialize an index (digit of units)
    index = len(digits) - 1
     
    # while the index is valid and the value at [index] ==
    # 9 set it as 0
    while (index >= 0 and digits[index] == 9):
        digits[index] = 0
        index -= 1
         
    # if index < 0 (if all digits were 9)
    if (index < 0):
       
        # insert an one at the beginning of the vector
        digits.insert(0, 1)
         
    # else increment the value at [index]
    else:
        digits[index]+=1
 
 
digits = [1, 7, 8, 9]
 
AddOne(digits)
 
for digit in digits:
    print(digit, end =' ')
     
# This code is contributed
# by Shubham Singh

// C# implementation for adding one
// to number represented by digits
using System;
using System.Xml;
 
     
class GFG{
 
// Driver code
static void Main(string[] args)
{
    int[] digits = new int[] { 1, 7, 8, 9 };
 
    // Initialize an index (digit of units)
    int index = digits.Length - 1;
     
        // While the index is valid and the value at
        // [index] == 9 set it as 0
        while (index >= 0 && digits[index] == 9)
            digits[index--] = 0;
     
        // If index < 0 (if all digits were 9)
        if (index < 0)
        {
             
            // Insert an one at the beginning of the vector
            Array.Resize(ref digits, index + 1);
            digits[0] = 1;
        }   
     
        // Else increment the value at [index]
        else
            digits[index]++;
 
    foreach(int digit in digits)
        Console.Write(digit + " ");
}
}
 
// This code is contributed by Shubham Singh

<script>
// JavaScript implementation for Adding one
// to number represented by digits
 
// function for adding one to number
const AddOne = (digits) =>
{
 
    // initialize an index (digit of units)
    let index = digits.length -1;
 
    // while the index is valid and the value at [index] ==
    // 9 set it as 0
    while (index >= 0 && digits[index] == 9)
        digits[index--] = 0;
 
    // if index < 0 (if all digits were 9)
    if (index < 0)
        // insert an one at the beginning of the vector
        digits.insert(digits.begin(), 1, 1);
 
    // else increment the value at [index]
    else
        digits[index]++;
}
// driver code
 
let digits = [ 1, 7, 8, 9 ];
 
AddOne(digits);
 
for (let i = 0; i < digits.length; i++)
    document.write(`${digits[i]} `);
 
// This code is contributed by Shubham Singh
 
</script>

1 7 9 0 

Complejidad del tiempo : O(n), donde n es el número de dígitos.

Espacio Auxiliar : O(1)

Otro enfoque : 

En este enfoque, primero invertimos la array original y luego tomamos una variable de acarreo para almacenar el valor de acarreo.

Ahora comenzamos a iterar sobre la array desde el principio y simplemente agregamos 1 y llevamos al valor de esa array en ese índice. Después de esto, vamos a verificar si el valor de ese índice es mayor que 9, entonces podemos tomar el acarreo como el valor de las decenas y el valor en ese índice en la array será el valor presente en el otro lugar en el que simplemente continuamos.

if digits[i]>9 then carry = digits[i]/10 and digits[i]%=10
if digits[i]<=9 then carry = 0.

Seguimos haciendo esto hasta llegar al último de la array. Ahora, después de salir también, si el acarreo no es cero, entonces simplemente debemos agregar ese 1 a la array también y luego invertir nuevamente la array para obtener nuestra array original.

¿Cómo invertir una array?

Implementación:

// This Code represents one more approach to
// Add 1 to the number represents in the array.
// This code is contributed by Omkar Subhash Ghongade.
#include<bits/stdc++.h>
using namespace std;
 
void plus_one(vector<int> &digits,int n)
{
    // We are reversing the original arr
    // So that we need to iterate from Back.
    reverse(digits.begin(),digits.end());
    // Taking a carry variable in case if there is any carry
    int carry=0;
    for(int i=0;i<n;i++)
    {
        // initially  carry is 0 so this is base case
        if(i==0)
            digits[i]+=(1+carry);
        // If carry is not equal to zero it should be added to
        // array element at that position.
        else if(carry!=0)
            digits[i]+=carry;
        // Now to get carry, i.e.
        // If digits[i]>9 we get the value at tens place in carry
        // or else if digits[i]<9 carry will be 0
        carry=digits[i]/10;
        // Now if carry is not equal to 0
        // so at that index we should keep the value present
        // at the ones place so we di digits[i]%10
        if(carry!=0)
            digits[i]=digits[i]%10;
    }
    // Afte doing all that if carry is still there which means
    // one more element is needed to be added to the array
    if(carry!=0)
        digits.push_back(carry);
    // Now we reverse the array so that we get the final array
    reverse(digits.begin(),digits.end());
}
 
int main()
{
    vector<int> digits={9,8,9,9};
    int n=digits.size();
    plus_one(digits,n);
    for(int i=0;i<digits.size();i++)
    {
        cout<<digits[i]<<" ";
    }
}

// This Code represents one more approach to
// Add 1 to the number represents in the array.
// This code is contributed by Omkar Subhash Ghongade.
import java.io.*;
import java.util.*;
class GFG {
 
  public static void plus_one(Vector<Integer> digits,int n)
  {
 
    // We are reversing the original arr
    // So that we need to iterate from Back.
    Collections.reverse(digits);
 
    // Taking a carry variable in case if there is any carry
    int carry = 0;
    for(int i = 0; i < n; i++)
    {
 
      // initially  carry is 0 so this is base case
      if(i == 0)
        digits.set(i, digits.get(i) + 1 + carry);
 
      // If carry is not equal to zero it should be added to
      // array element at that position.
      else if(carry != 0)
        digits.set(i, digits.get(i) + carry);
 
      // Now to get carry, i.e.
      // If digits[i]>9 we get the value at tens place in carry
      // or else if digits[i]<9 carry will be 0
      carry = digits.get(i) / 10;
 
      // Now if carry is not equal to 0
      // so at that index we should keep the value present
      // at the ones place so we di digits[i]%10
      if(carry != 0)
        digits.set(i, digits.get(i) % 10);
    }
 
    // Afte doing all that if carry is still there which means
    // one more element is needed to be added to the array
    if(carry != 0)
      digits.set(digits.size() - 1, carry);
 
    // Now we reverse the array so that we get the final array
    Collections.reverse(digits);
  }
 
  public static void main (String[] args)
  {
    Vector<Integer> digits = new Vector<Integer>(Arrays.asList(9,8,9,9));
    int n = digits.size();
    plus_one(digits, n);
    for(int i = 0; i < n; i++)
    {
      System.out.print(digits.get(i) + " ");
    }
  }
}
 
// This code is contributed by Shubham Singh

# This Code represents one more approach to
# Add 1 to the number represents in the array.
def plus_one(digits, n):
   
    # We are reversing the original arr
    # So that we need to iterate from Back.
    digits.reverse()
     
    # Taking a carry variable in case if there is any carry
    carry = 0
     
    for i in range(n):
         
        # initially  carry is 0 so this is base case
        if(i == 0):
            digits[i] += (1 + carry)
         
        # If carry is not equal to zero it should be added to
        # array element at that position.
        elif(carry != 0):
            digits[i] += carry
             
        # Now to get carry, i.e.
        # If digits[i]>9 we get the value at tens place in carry
        # or else if digits[i]<9 carry will be 0
        carry = digits[i]//10
         
        # Now if carry is not equal to 0
        # so at that index we should keep the value present
        # at the ones place so we di digits[i]%10
        if(carry != 0):
            digits[i] = digits[i] % 10
             
    # Afte doing all that if carry is still there which means
    # one more element is needed to be added to the array
    if(carry != 0):
        digits.append(carry)
         
    # Now we reverse the array so that we get the final array
    digits.reverse()
 
# Driver code
digits = [9, 8, 9, 9]
n = len(digits)
plus_one(digits, n)
 
for i in digits:
    print(i, end =" ")
     
# This code is contributed
# by Shubham Singh

// This Code represents one more approach to
// Add 1 to the number represents in the array.
 
using System;
 
public class GFG{
 
  public static void Main ()
  {
    int[] digits = new int[] {9,8,9,9};
    int n = digits.Length;
     
    // We are reversing the original arr
    // So that we need to iterate from Back.
    Array.Reverse(digits);
 
    // Taking a carry variable in case if there is any carry
    int carry = 0;
    for(int i = 0; i < n; i++)
    {
 
      // initially  carry is 0 so this is base case
      if(i == 0)
        digits[i] = digits[i] + 1 + carry;
 
      // If carry is not equal to zero it should be added to
      // array element at that position.
      else if(carry != 0)
        digits[i] = digits[i] + carry;
 
      // Now to get carry, i.e.
      // If digits[i]>9 we get the value at tens place in carry
      // or else if digits[i]<9 carry will be 0
      carry = digits[i] / 10;
 
      // Now if carry is not equal to 0
      // so at that index we should keep the value present
      // at the ones place so we di digits[i]%10
      if(carry != 0)
        digits[i] = digits[i]%10;
    }
 
    // Afte doing all that if carry is still there which means
    // one more element is needed to be added to the array
    if(carry != 0)
      digits[digits.Length -1] = carry;
 
    // Now we reverse the array so that we get the final array
    Array.Reverse(digits);
     
    for(int i = 0; i < n; i++)
    {
      Console.Write(digits[i] + " ");
    }
     
  }
}
 
// This code is contributed by Shubham Singh

<script>
// This Code represents one more approach to
// Add 1 to the number represents in the array.
 
var digits = [9,8,9,9];
var n = digits.length;
 
// We are reversing the original arr
// So that we need to iterate from Back.
digits.reverse();
 
// Taking a carry variable in case if there is any carry
var carry = 0;
for(var i = 0; i < n; i++)
{
    // initially  carry is 0 so this is base case
    if(i == 0)
        digits[i] = digits[i] + 1 + carry;
    // If carry is not equal to zero it should be added to
    // array element at that position.
    else if(carry != 0)
        digits[i] = digits[i] + carry;
        
    // Now to get carry, i.e.
    // If digits[i]>9 we get the value at tens place in carry
    // or else if digits[i]<9 carry will be 0
    carry = parseInt(digits[i] / 10);
     
    // Now if carry is not equal to 0
    // so at that index we should keep the value present
    // at the ones place so we di digits[i]%10
    if(carry != 0)
        digits[i] = digits[i]%10;
}
 
// Afte doing all that if carry is still there which means
// one more element is needed to be added to the array
if(carry != 0)
    digits[digits.length -1] = carry;
 
// Now we reverse the array so that we get the final array
digits.reverse();
 
for(var i = 0; i < n; i++)
{
    document.write(digits[i] + " ");
}
 
 
// This code is contributed by Shubham Singh
</script>

9 9 0 0 

Complejidad de tiempo : O(n), donde n es el tamaño de la array.

Espacio Auxiliar : O(1)