Given an array of numbers, return an array of the products of allI offer two solutions, both beautiful and hideous in their own ways.otherelements in the array.

More formally, write a method`int[] products(int...)`

, where`products(nums)[i]`

is the product of all`nums[j], j != i`

.

System.out.println( java.util.Arrays.toString( products(1, 2, 3, 4, 5) ) ); // prints "[120, 60, 40, 30, 24]" // i.e. [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]You must do this in`O(N)`

without using division.

## Iterative

static int[] products(int... nums) { final int N = nums.length; int[] prods = new int[N]; java.util.Arrays.fill(prods, 1); for (int // pi----> * <----pj i = 0, pi = 1 , j = N-1, pj = 1 ; (i < N) & (j >= 0) ; pi *= nums[i++] , pj *= nums[j--] ) { prods[i] *= pi ; prods[j] *= pj ; } return prods; }

`O(N)`

space for output, `O(1)`

temporary, `O(N)`

time, no division. The formatting betrays all conventions, but self-documentation doesn't get any more poetic than this.## Recursive

static int[] products(int... nums) { products(nums, 1, 0); return nums; } static int products(int[] nums, int p, int n) { return (n == nums.length) ? 1 : nums[n] * (p = products(nums, nums[n] * (nums[n] = p), n + 1)) + 0*(nums[n] *= p); }

*In-place modification*of the input array,

`O(N)`

temporary space on the stack, `O(N)`

time, no division. The less said about it the better.
Beautiful solutions. Another way of expressing the, somewhat odd looking constraint "no division" would perhaps be to say that one should be able to handle situations in which the product of all input numbers exceed Integer.MAX_VALUE.

ReplyDeletea call such as products(46340, 46340, 46340) fails miserably if it's naively implemented with division!

Another case where the division algorithm would fail is if the array contains a zero.

ReplyDelete