Dadas dos arrays A[0….n-1] y B[0….m-1] de tamaño n y m respectivamente, que representan dos números tales que cada elemento de las arrays representa un dígito. Por ejemplo, A[] = { 1, 2, 3} y B[] = { 2, 1, 4 } representan 123 y 214 respectivamente. La tarea es encontrar la suma de ambos el número. En el caso anterior, la respuesta es 337.
Ejemplos:
Input : n = 3, m = 3
a[] = { 1, 2, 3 }
b[] = { 2, 1, 4 }
Output : 337
123 + 214 = 337
Input : n = 4, m = 3
a[] = { 9, 5, 4, 9 }
b[] = { 2, 1, 4 }
Output : 9763
La idea es comenzar a recorrer ambos arreglos simultáneamente desde el final hasta llegar al índice 0 de cualquiera de los arreglos. Mientras recorre cada elemento de la array, agregue elementos de la array y lleve de la suma anterior. Ahora almacene el dígito de la unidad de la suma y avance para la próxima suma de índice. Mientras agrega el elemento de índice 0 si el acarreo se fue, luego agréguelo al comienzo del número.
A continuación se muestra la ilustración del enfoque:
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to sum two numbers represented two
// arrays.
#include <bits/stdc++.h>
using namespace std;
// Return sum of two number represented by the arrays.
// Size of a[] is greater than b[]. It is made sure
// be the wrapper function
int calSumUtil(int a[], int b[], int n, int m)
{
// array to store sum.
int sum[n];
int i = n - 1, j = m - 1, k = n - 1;
int carry = 0, s = 0;
// Until we reach beginning of array.
// we are comparing only for second array
// because we have already compare the size
// of array in wrapper function.
while (j >= 0) {
// find sum of corresponding element
// of both arrays.
s = a[i] + b[j] + carry;
sum[k] = (s % 10);
// Finding carry for next sum.
carry = s / 10;
k--;
i--;
j--;
}
// If second array size is less the first
// array size.
while (i >= 0) {
// Add carry to first array elements.
s = a[i] + carry;
sum[k] = (s % 10);
carry = s / 10;
i--;
k--;
}
int ans = 0;
// If there is carry on adding 0 index elements.
// append 1 to total sum.
if (carry)
ans = 10;
// Converting array into number.
for (int i = 0; i <= n - 1; i++) {
ans += sum[i];
ans *= 10;
}
return ans / 10;
}
// Wrapper Function
int calSum(int a[], int b[], int n, int m)
{
// Making first array which have
// greater number of element
if (n >= m)
return calSumUtil(a, b, n, m);
else
return calSumUtil(b, a, m, n);
}
// Driven Program
int main()
{
int a[] = { 9, 3, 9 };
int b[] = { 6, 1 };
int n = sizeof(a) / sizeof(a[0]);
int m = sizeof(b) / sizeof(b[0]);
cout << calSum(a, b, n, m) << endl;
return 0;
}
Java
// Java program to sum two numbers
// represented two arrays.
import java.io.*;
class GFG {
// Return sum of two number represented by
// the arrays. Size of a[] is greater than
// b[]. It is made sure be the wrapper
// function
static int calSumUtil(int a[], int b[],
int n, int m)
{
// array to store sum.
int[] sum= new int[n];
int i = n - 1, j = m - 1, k = n - 1;
int carry = 0, s = 0;
// Until we reach beginning of array.
// we are comparing only for second
// array because we have already compare
// the size of array in wrapper function.
while (j >= 0)
{
// find sum of corresponding element
// of both array.
s = a[i] + b[j] + carry;
sum[k] = (s % 10);
// Finding carry for next sum.
carry = s / 10;
k--;
i--;
j--;
}
// If second array size is less
// the first array size.
while (i >= 0)
{
// Add carry to first array elements.
s = a[i] + carry;
sum[k] = (s % 10);
carry = s / 10;
i--;
k--;
}
int ans = 0;
// If there is carry on adding 0 index
// elements append 1 to total sum.
if (carry == 1)
ans = 10;
// Converting array into number.
for ( i = 0; i <= n - 1; i++) {
ans += sum[i];
ans *= 10;
}
return ans / 10;
}
// Wrapper Function
static int calSum(int a[], int b[], int n,
int m)
{
// Making first array which have
// greater number of element
if (n >= m)
return calSumUtil(a, b, n, m);
else
return calSumUtil(b, a, m, n);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int a[] = { 9, 3, 9 };
int b[] = { 6, 1 };
int n = a.length;
int m = b.length;
System.out.println(calSum(a, b, n, m));
}
}
// This article is contributed by Gitanjali.
Python3
# Python3 code to sum two numbers # representer two arrays. # Return sum of two number represented # by the arrays. Size of a[] is greater # than b[]. It is made sure be the # wrapper function def calSumUtil( a , b , n , m ): # array to store sum. sum = [0] * n i = n - 1 j = m - 1 k = n - 1 carry = 0 s = 0 # Until we reach beginning of array. # we are comparing only for second array # because we have already compare the size # of array in wrapper function. while j >= 0: # find sum of corresponding element # of both array. s = a[i] + b[j] + carry sum[k] = (s % 10) # Finding carry for next sum. carry = s // 10 k-=1 i-=1 j-=1 # If second array size is less the first # array size. while i >= 0: # Add carry to first array elements. s = a[i] + carry sum[k] = (s % 10) carry = s // 10 i-=1 k-=1 ans = 0 # If there is carry on adding 0 index elements. # append 1 to total sum. if carry: ans = 10 # Converting array into number. for i in range(n): ans += sum[i] ans *= 10 return ans // 10 # Wrapper Function def calSum(a, b, n, m ): # Making first array which have # greater number of element if n >= m: return calSumUtil(a, b, n, m) else: return calSumUtil(b, a, m, n) # Driven Code a = [ 9, 3, 9 ] b = [ 6, 1 ] n = len(a) m = len(b) print(calSum(a, b, n, m)) # This code is contributed by "Sharad_Bhardwaj".
C#
// C# program to sum two numbers
// represented two arrays.
using System;
class GFG {
// Return sum of two number represented by
// the arrays. Size of a[] is greater than
// b[]. It is made sure be the wrapper
// function
static int calSumUtil(int []a, int []b,
int n, int m)
{
// array to store sum.
int[] sum= new int[n];
int i = n - 1, j = m - 1, k = n - 1;
int carry = 0, s = 0;
// Until we reach beginning of array.
// we are comparing only for second
// array because we have already compare
// the size of array in wrapper function.
while (j >= 0)
{
// find sum of corresponding element
// of both array.
s = a[i] + b[j] + carry;
sum[k] = (s % 10);
// Finding carry for next sum.
carry = s / 10;
k--;
i--;
j--;
}
// If second array size is less
// the first array size.
while (i >= 0)
{
// Add carry to first array elements.
s = a[i] + carry;
sum[k] = (s % 10);
carry = s / 10;
i--;
k--;
}
int ans = 0;
// If there is carry on adding 0 index
// elements append 1 to total sum.
if (carry == 1)
ans = 10;
// Converting array into number.
for ( i = 0; i <= n - 1; i++) {
ans += sum[i];
ans *= 10;
}
return ans / 10;
}
// Wrapper Function
static int calSum(int []a, int []b, int n,
int m)
{
// Making first array which have
// greater number of element
if (n >= m)
return calSumUtil(a, b, n, m);
else
return calSumUtil(b, a, m, n);
}
// Driver program
public static void Main()
{
int []a = { 9, 3, 9 };
int []b = { 6, 1 };
int n = a.Length;
int m = b.Length;
Console.WriteLine(calSum(a, b, n, m));
}
}
// This article is contributed by vt_m.
PHP
<?php
// PHP program to sum two numbers
// represented two arrays.
// Return sum of two number represented
// by the arrays. Size of a[] is greater
// than b[]. It is made sure be the
// wrapper function
function calSumUtil($a, $b, $n, $m)
{
// array to store sum.
$sum = array();
$i = $n - 1; $j = $m - 1; $k = $n - 1;
$carry = 0; $s = 0;
// Until we reach beginning of array.
// we are comparing only for second array
// because we have already compare the size
// of array in wrapper function.
while ($j >= 0)
{
// find sum of corresponding
// element of both array.
$s = $a[$i] + $b[$j] + $carry;
$sum[$k] = ($s % 10);
// Finding carry for next sum.
$carry = $s / 10;
$k--;
$i--;
$j--;
}
// If second array size is less
// than the first array size.
while ($i >= 0)
{
// Add carry to first array elements.
$s = $a[$i] + $carry;
$sum[$k] = ($s % 10);
$carry = $s / 10;
$i--;
$k--;
}
$ans = 0;
// If there is carry on
// adding 0 index elements.
// append 1 to total sum.
if ($carry)
$ans = 10;
// Converting array into number.
for ( $i = 0; $i <= $n - 1; $i++)
{
$ans += $sum[$i];
$ans *= 10;
}
return $ans / 10;
}
// Wrapper Function
function calSum( $a, $b, $n, $m)
{
// Making first array which have
// greater number of element
if ($n >= $m)
return calSumUtil($a, $b, $n, $m);
else
return calSumUtil($b, $a, $m, $n);
}
// Driven Code
$a = array( 9, 3, 9 );
$b = array( 6, 1 );
$n = count($a);
$m = count($b);
echo calSum($a, $b, $n, $m);
// This article is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to sum two numbers represented two
// arrays.
// Return sum of two number represented by the arrays.
// Size of a[] is greater than b[]. It is made sure
// be the wrapper function
function calSumUtil(a, b, n, m)
{
// array to store sum.
let sum = new Array(n);
let i = n - 1, j = m - 1, k = n - 1;
let carry = 0, s = 0;
// Until we reach beginning of array.
// we are comparing only for second array
// because we have already compare the size
// of array in wrapper function.
while (j >= 0) {
// find sum of corresponding element
// of both arrays.
s = a[i] + b[j] + carry;
sum[k] = (s % 10);
// Finding carry for next sum.
carry = Math.floor(s / 10);
k--;
i--;
j--;
}
// If second array size is less the first
// array size.
while (i >= 0) {
// Add carry to first array elements.
s = a[i] + carry;
sum[k] = (s % 10);
carry = Math.floor(s / 10);
i--;
k--;
}
let ans = 0;
// If there is carry on adding 0 index elements.
// append 1 to total sum.
if (carry)
ans = 10;
// Converting array into number.
for (let i = 0; i <= n - 1; i++) {
ans += sum[i];
ans *= 10;
}
return ans / 10;
}
// Wrapper Function
function calSum(a, b, n, m)
{
// Making first array which have
// greater number of element
if (n >= m)
return calSumUtil(a, b, n, m);
else
return calSumUtil(b, a, m, n);
}
// Driven Program
let a = [ 9, 3, 9 ];
let b = [ 6, 1 ];
let n = a.length;
let m = b.length;
document.write(calSum(a, b, n, m) + "<br>");
// This code is contributed by Mayank Tyagi
</script>
Producción
1000
Complejidad de Tiempo: O(n + m)
Espacio Auxiliar: O(max(n, m))