Hello Friends, the problem covered in this article is very interesting. This can be solved in many ways but we have to solve it in best optimal way.
This problem was asked by Uber.
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [ 2, 3, 5, 4], the expected output would be [60, 40, 24, 30]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Follow-up: what if you can’t use division?
Solution for Daily Coding Problem – 2
As I mentioned this problem can be solved in many ways. One way would be to traverse the whole array and find the product of all the elements in apart from current element in an inner array. But the time complexity of the solution would be O(n power of 2).
The logic behind the solution of this problem would be to divide the solution in two parts. From the problem statement we can see that the multiplication of elements for any index would be the multiplication of array at the left side of element and multiplication of right side of element.
Thinking on the same lines we need to have two arrays. The first array will contain the multiplication of the left elements. The next array will contain the multiplication of right elements.
It should be more clear by below figure.
The left elements product array contains the product of all the elements at left side. Similarly right elements product contains the product of elements at right side.
If we want to find the product of element apart from the current index element, we can multiply the previous and next element to get the product.
Code Examples in C# and Java
Below are code examples in C# and Java
Java:
Conclusion:
The Daily Coding Problem – 2 was clearly a good candidate for analytical thinking and how a candidate can come up with innovative way to solve the problem.