Kun on annettu kaksi kokonaislukutaulukkoa, lisää niiden elementit kolmanteen taulukkoon täyttämällä seuraavat rajoitukset -
- Lisäys tulee tehdä molempien taulukoiden 0. indeksistä.
- Jaa summa, jos se ei ole yksinumeroinen luku, ja tallenna numerot vierekkäisiin paikkoihin lähtötaulukossa.
- Lähtötaulukon tulisi sisältää kaikki jäljellä olevat numerot suuremmasta tulotaulukosta.
Esimerkkejä:
Input: a = [9 2 3 7 9 6] b = [3 1 4 7 8 7 6 9] Output: [1 2 3 7 1 4 1 7 1 3 6 9] Input: a = [9343 2 3 7 9 6] b = [34 11 4 7 8 7 6 99] Output: [9 3 7 7 1 3 7 1 4 1 7 1 3 6 9 9] Input: a = [] b = [11 2 3 ] Output: [1 1 2 3 ] Input: a = [9 8 7 6 5 4 3 2 1] b = [1 2 3 4 5 6 7 8 9] Output: [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
Vaikeustaso: Alokas
Idea on hyvin yksinkertainen. Ylläpidämme lähtötaulukkoa ja suoritamme silmukan molempien taulukoiden 0. indeksistä. Jokaiselle silmukan iteraatiolle otetaan huomioon molempien taulukoiden seuraavat elementit ja lisätään ne. Jos summa on suurempi kuin 9, työnnämme summan yksittäiset numerot lähtötaulukkoon, muuten työnnämme itse summan. Lopuksi työnnämme suuremman syöttötaulukon loput elementit lähtötaulukkoon.
Alla yllä olevan idean toteutus:
ddl vs dmlC++
// C++ program to add two arrays following given // constraints #include using namespace std; // Function to push individual digits of a number // to output vector from left to right void split(int num vector<int> &out) { vector<int> arr; while (num) { arr.push_back(num%10); num = num/10; } // reverse the vector arr and append it to output vector out.insert(out.end() arr.rbegin() arr.rend()); } // Function to add two arrays keeping given // constraints void addArrays(int arr1[] int arr2[] int m int n) { // create a vector to store output vector<int> out; // maintain a variable to store current index in // both arrays int i = 0; // loop till arr1 or arr2 runs out while (i < m && i < n) { // read next elements from both arrays and // add them int sum = arr1[i] + arr2[i]; // if sum is single digit number if (sum < 10) out.push_back(sum); else { // if sum is not a single digit number push // individual digits to output vector split(sum out); } // increment to next index i++; } // push remaining elements of first input array // (if any) to output vector while (i < m) split(arr1[i++] out); // push remaining elements of second input array // (if any) to output vector while (i < n) split(arr2[i++] out); // print the output vector for (int x : out) cout << x << ' '; } // Driver code int main() { int arr1[] = {9343 2 3 7 9 6}; int arr2[] = {34 11 4 7 8 7 6 99}; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); addArrays(arr1 arr2 m n); return 0; }
Java // Java program to add two arrays following given // constraints import java.util.Vector; class GFG { // Function to push individual digits of a number // to output vector from left to right static void split(int num Vector<Integer> out) { Vector<Integer> arr = new Vector<>(); while (num > 0) { arr.add(num % 10); num /= 10; } // reverse the vector arr and // append it to output vector for (int i = arr.size() - 1; i >= 0; i--) out.add(arr.elementAt(i)); } // Function to add two arrays keeping given // constraints static void addArrays(int[] arr1 int[] arr2 int m int n) { // create a vector to store output Vector<Integer> out = new Vector<>(); // maintain a variable to store // current index in both arrays int i = 0; // loop till arr1 or arr2 runs out while (i < m && i < n) { // read next elements from both arrays // and add them int sum = arr1[i] + arr2[i]; // if sum is single digit number if (sum < 10) out.add(sum); else // if sum is not a single digit number // push individual digits to output vector split(sum out); // increment to next index i++; } // push remaining elements of first input array // (if any) to output vector while (i < m) split(arr1[i++] out); // push remaining elements of second input array // (if any) to output vector while (i < n) split(arr2[i++] out); // print the output vector for (int x : out) System.out.print(x + ' '); } // Driver Code public static void main(String[] args) { int[] arr1 = { 9343 2 3 7 9 6 }; int[] arr2 = { 34 11 4 7 8 7 6 99 }; int m = arr1.length; int n = arr2.length; addArrays(arr1 arr2 m n); } } // This code is contributed by // sanjeev2552
Python3 # Python program to add two arrays # following given constraints # Function to push individual digits # of a number to output list from # left to right def split(num out): arr = [] while num: arr.append(num % 10) num = num // 10 for i in range(len(arr) - 1 -1 -1): out.append(arr[i]) # Function to add two arrays keeping given # constraints def add_arrays(arr1 arr2 m n): # Create a list to store output out = [] # Maintain a variable to store # current index in both arrays i = 0 # Loop till arr1 or arr2 runs out while i < m and i < n: # Read next elements from both # arrays and add them sum = arr1[i] + arr2[i] # If sum is single digit number if sum < 10: out.append(sum) else: # If sum is not a single digit # number push individual digits # to output list split(sum out) # Increment to next index i += 1 # Push remaining elements of first # input array (if any) to output list while i < m: split(arr1[i] out) i += 1 # Push remaining elements of second # input array (if any) to output list while i < n: split(arr2[i] out) i += 1 # Print the output list for x in out: print(x end = ' ') # Driver code arr1 = [9343 2 3 7 9 6] arr2 = [34 11 4 7 8 7 6 99] m = len(arr1) n = len(arr2) add_arrays(arr1 arr2 m n) # This code is contributed by akashish__
C# // C# program to add two arrays following given // constraints using System; using System.Collections.Generic; class GFG { // Function to push individual digits of a number // to output vector from left to right static void split(int num List<int> outs) { List<int> arr = new List<int>(); while (num > 0) { arr.Add(num % 10); num /= 10; } // reverse the vector arr and // append it to output vector for (int i = arr.Count - 1; i >= 0; i--) outs.Add(arr[i]); } // Function to add two arrays keeping given // constraints static void addArrays(int[] arr1 int[] arr2 int m int n) { // create a vector to store output List<int> outs = new List<int>(); // maintain a variable to store // current index in both arrays int i = 0; // loop till arr1 or arr2 runs out while (i < m && i < n) { // read next elements from both arrays // and add them int sum = arr1[i] + arr2[i]; // if sum is single digit number if (sum < 10) outs.Add(sum); else // if sum is not a single digit number // push individual digits to output vector split(sum outs); // increment to next index i++; } // push remaining elements of first input array // (if any) to output vector while (i < m) split(arr1[i++] outs); // push remaining elements of second input array // (if any) to output vector while (i < n) split(arr2[i++] outs); // print the output vector foreach (int x in outs) Console.Write(x + ' '); } // Driver Code public static void Main(String[] args) { int[] arr1 = { 9343 2 3 7 9 6 }; int[] arr2 = { 34 11 4 7 8 7 6 99 }; int m = arr1.Length; int n = arr2.Length; addArrays(arr1 arr2 m n); } } // This code is contributed by PrinciRaj1992
JavaScript <script> // Javascript program to add two arrays // following given constraints // Function to push individual digits // of a number to output vector from // left to right function split(num out) { let arr = []; while (num) { arr.push(num % 10); num = Math.floor(num / 10); } for(let i = arr.length - 1; i >= 0; i--) out.push(arr[i]); } // Function to add two arrays keeping given // constraints function addArrays(arr1 arr2 m n) { // Create a vector to store output let out = []; // Maintain a variable to store // current index in both arrays let i = 0; // Loop till arr1 or arr2 runs out while (i < m && i < n) { // Read next elements from both // arrays and add them let sum = arr1[i] + arr2[i]; // If sum is single digit number if (sum < 10) out.push(sum); else { // If sum is not a single digit // number push individual digits // to output vector split(sum out); } // Increment to next index i++; } // Push remaining elements of first // input array (if any) to output vector while (i < m) split(arr1[i++] out); // Push remaining elements of second // input array (if any) to output vector while (i < n) split(arr2[i++] out); // Print the output vector for(let x of out) document.write(x + ' '); } // Driver code let arr1 = [ 9343 2 3 7 9 6 ]; let arr2 = [ 34 11 4 7 8 7 6 99 ]; let m = arr1.length; let n = arr2.length; addArrays(arr1 arr2 m n); // This code is contributed by _saurabh_jaiswal </script>
Lähtö
9 3 7 7 1 3 7 1 4 1 7 1 3 6 9 9
Aika monimutkaisuus yllä olevan ratkaisun ratkaisu on O(m + n), kun kuljemme molemmat taulukot tarkalleen kerran.
Tapa 2 (käyttäen merkkijonoa ja STL:ää):
tässä lähestymistavassa otamme yhden merkkijonon nimeltä "ans". kun lisäämme molempien taulukoiden elementin, tuloksena oleva summa muunnetaan merkkijonoksi ja tähän merkkijonoon lisätään päämerkkijono "ans".
Kun olet tehnyt tämän kaikille elementeille, otamme yhden vektorin ja siirrämme koko merkkijonon kyseiseen vektoriin ja lopuksi tulostamme sen vektorin.
powershell-järjestelmänvalvoja
Alla on yllä olevan lähestymistavan toteutus:
C++// C++ program to add two arrays // following given constrains #include using namespace std; // function to add two arrays // following given constrains void creat_new(int arr1[] int arr2[] int n int m) { string ans; int i = 0; while (i < min(n m)) { // adding the elements int sum = arr1[i] + arr2[i]; // converting the integer to string string s = to_string(sum); // appending the string ans += s; i++; } // entering remaining element(if any) of // first array for (int j = i; j < n; j++) { string s = to_string(arr1[j]); ans += s; } // entering remaining element (if any) of // second array for (int j = i; j < m; j++) { string s = to_string(arr2[j]); ans += s; } // taking vector vector<int> k; // assigning the elements of string // to vector for (int i = 0; i < ans.length(); i++) { k.push_back(ans[i] - '0'); } // printing the elements of vector for (int i = 0; i < k.size(); i++) { cout << k[i] << ' '; } } // driver code int main() { int arr1[] = { 9 2 3 7 9 6 }; int arr2[] = { 3 1 4 7 8 7 6 9 }; int n = sizeof(arr1) / sizeof(arr1[0]); int m = sizeof(arr2) / sizeof(arr2[0]); // function call creat_new(arr1 arr2 n m); return 0; } // this code is contributed by Machhaliya Muhammad
Java /*package whatever //do not write package name here */ import java.util.*; class GFG { // function to add two arrays // following given constrains static void creat_new(int arr1[] int arr2[] int n int m) { String ans = ''; int i = 0; while (i < Math.min(n m)) { // adding the elements int sum = arr1[i] + arr2[i]; // converting the integer to string String s = sum + ''; // appending the string ans += s; i++; } // entering remaining element(if any) of // first array for (int j = i; j < n; j++) { String s = arr1[j] + ''; ans += s; } // entering remaining element (if any) of // second array for (int j = i; j < m; j++) { String s = arr2[j] + ''; ans += s; } // taking vector ArrayList<Integer> k = new ArrayList<>(); // assigning the elements of string // to vector for (int j = 0; j < ans.length(); j++) { k.add(ans.charAt(j) - '0'); } // printing the elements of vector for (int j = 0; j < k.size(); j++) { System.out.print(k.get(j) + ' '); } } public static void main(String[] args) { int arr1[] = { 9 2 3 7 9 6 }; int arr2[] = { 3 1 4 7 8 7 6 9 }; int n = arr1.length; int m = arr2.length; // function call creat_new(arr1 arr2 n m); } } // This code is contributed by aadityaburujwale.
Python3 import math class GFG : # function to add two arrays # following given constrains @staticmethod def creat_new( arr1 arr2 n m) : ans = '' i = 0 while (i < min(nm)) : # adding the elements sum = arr1[i] + arr2[i] # converting the integer to string s = str(sum) + '' # appending the string ans += s i += 1 # entering remaining element(if any) of # first array j = i while (j < n) : s = str(arr1[j]) + '' ans += s j += 1 # entering remaining element (if any) of # second array j = i while (j < m) : s = str(arr2[j]) + '' ans += s j += 1 # taking vector k = [] # assigning the elements of string # to vector j = 0 while (j < len(ans)) : k.append(ord(ans[j]) - ord('0')) j += 1 # printing the elements of vector j = 0 while (j < len(k)) : print(k[j]end=' ') j += 1 @staticmethod def main( args) : arr1 = [9 2 3 7 9 6] arr2 = [3 1 4 7 8 7 6 9] n = len(arr1) m = len(arr2) # function call GFG.creat_new(arr1 arr2 n m) if __name__=='__main__': GFG.main([]) # This code is contributed by aadityaburujwale.
C# // Include namespace system using System; using System.Collections.Generic; public class GFG { // function to add two arrays // following given constrains public static void creat_new(int[] arr1 int[] arr2 int n int m) { var ans = ''; var i = 0; while (i < Math.Min(nm)) { // adding the elements var sum = arr1[i] + arr2[i]; // converting the integer to string var s = sum.ToString() + ''; // appending the string ans += s; i++; } // entering remaining element(if any) of // first array for (int j = i; j < n; j++) { var s = arr1[j].ToString() + ''; ans += s; } // entering remaining element (if any) of // second array for (int j = i; j < m; j++) { var s = arr2[j].ToString() + ''; ans += s; } // taking vector var k = new List<int>(); // assigning the elements of string // to vector for (int j = 0; j < ans.Length; j++) { k.Add((int)(ans[j]) - (int)('0')); } // printing the elements of vector for (int j = 0; j < k.Count; j++) { Console.Write(k[j] + ' '); } } public static void Main(String[] args) { int[] arr1 = {9 2 3 7 9 6}; int[] arr2 = {3 1 4 7 8 7 6 9}; var n = arr1.Length; var m = arr2.Length; // function call GFG.creat_new(arr1 arr2 n m); } } // This code is contributed by aadityaburujwale.
JavaScript // JavaScript Code // function to add two arrays // following given constrains const creat_new = (arr1 arr2 n m) => { let ans = ''; let i = 0; while (i < Math.min(n m)) { // adding the elements let sum = arr1[i] + arr2[i]; // converting the integer to string let s = sum.toString(); // appending the string ans += s; i++; } // entering remaining element(if any) of // first array for (let j = i; j < n; j++) { let s = arr1[j].toString(); ans += s; } // entering remaining element (if any) of // second array for (let j = i; j < m; j++) { let s = arr2[j].toString(); ans += s; } // taking vector let k = []; // assigning the elements of string // to vector for (let i = 0; i < ans.length; i++) { k.push(parseInt(ans[i])); } // printing the elements of vector console.log(k); } // Driver code let arr1 = [9 2 3 7 9 6]; let arr2 = [3 1 4 7 8 7 6 9]; let n = arr1.length; let m = arr2.length; // function call creat_new(arr1 arr2 n m); // This code is contributed by akashish__
Lähtö
1 2 3 7 1 4 1 7 1 3 6 9
Aika monimutkaisuus: O(max(min))
Aputila: O(m+n) koska vektori k (koko m+n pahimmassa tapauksessa) luodaan.