Hello, here is my code :
Now , I don’t know how should I proceed further? Need some help regarding the further approach.
Doubt in my code
Hey Yash , this problem can be approached by using two approach, one is from starting of the array, you iterate with all the elements and other is from back of the array, you iterate all the elements. Which approach you want me to explain you?
Yes I want to use the second approach.
Suppose you have input like this:
5
9 9 9 9 9
5
9 9 9 9 9
How will you approach this problem?
We have to do this question in such a manner that every cell of an array doesn’t go beyond number 9, if you will do so you will see
Cell 1 from right 9+9 = 18, 8 in cell . One in carry.
Cell 2 from right 1+9+9 = 19, 9 in cell . One in carry.
Cell 3 from right 1+9+9 = 19, 9 in cell . One in carry.
Cell 4 from right 1+9+9 = 19, 9 in cell . One in carry.
Cell 5 from right 1+9+9 = 19, 19 in cell . Array index ends.
Yes, this is the exact thought in my mind but the problem arises when I want to store in the third array whose size is not known to me that how many digits it will contain after the sum. So how do I iterate over such a array from backside.
Find the maximum of size of both the array, I.e., maximum of N & M. Which ever is greater will be the size your final array.
But I think the size may be this one?
The size of largest array + 1(for the carry in worst case) ?
Yes, you can even do it like that, but what if last element doesn’t have any carry to give
What if case is
2 5 6 7
+ 2 3 4
2 8 0 1
That’s why I was recommending to use only the maximum size array cause last carry can be handled by using only if statement.
Ok so is there any optimized way to do this task?
This is the optimised way only, it’s O(N) . And this problem will take minimum of O(N) only. Can’t be reduced further.
1 Like
Ok thank you for your support 