michaelbarlow7
BAN USERI'm not sure this would work with the following input:
{ 1, 2, 4, 5, 6, 7, 3 }
Before the 3, the stack would look like this:
1, 2, 4, 5, 6, 7
But then the 3 would pop all the elements down to the 2 off the stack, so it would return:
1, 2, 3
The question asks us to find the product of all the other numbers in the array for each number.
We can model this by saying that the output for any number in the input array is equal to the product of all the numbers to the left of that number, multiplied by the product of all the numbers to the right of that number.
To cater for the edge cases, we can say that the product of numbers to the left of the first element is equal to 1, and similarly, the product of numbers to the right of the last element is also equal to 1.
We can find the products of numbers to the left of all the numbers in the array by maintaining a separate array that tracks the cumulative product of all the numbers to the left of the corresponding number in the input array (this is the "rear" array in the answer).
By setting the first number in this rear array to 1, we can easily calculate the rest of the cumulative products by iterating through and multiplying each number with the previous entry in the rear array.
Similarly, we can create the array of cumulative products from the right of the array (the "front" array) by iterating from right to left.
Once we have this, we can then create our output array by multiplying the corresponding rear entry with its corresponding front entry.
Each pass consists of n operations, so its complexity is O(n).
Good solution, except the end should be:
head = prev
since prev would be pointing to the head of the linked-list at this point (current would be pointing to null in order to escape the while loop).
- michaelbarlow7 February 25, 2015
I agree, this question is pretty poorly worded. I interpreted it the same way as you.
For those that were wondering what "WAP" means, I think it's short for "Write A Program". Why the poster felt the need to abbreviate that is beyond me.
I think the problem could be better stated as:
Given an unsorted array of n integers from 0 to n-1 (int[] input), return an output array (int[] output) such that
This should be done with O(n) time complexity and O(1) space complexity (so it needs to be done "in-place" in the input array).
- michaelbarlow7 March 02, 2015