To split a number into an array:Convert the number to a string. Use the Array. from() method to convert the string into an array of digits. Use the map() function to convert each string in the array to a number.
An explanation of polygenelubricants method is: The trick is to construct the arrays (in the case for 4 elements)
{ 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], }
{ a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, }
Both of which can be done in O(n) by starting at the left and right edges respectively.
Then multiplying the two arrays element by element gives the required result
My code would look something like this:
int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i) {
products_below[i]=p;
p*=a[i];
}
int products_above[N];
p=1;
for(int i=N-1;i>=0;--i) {
products_above[i]=p;
p*=a[i];
}
int products[N]; // This is the result
for(int i=0;i<N;++i) {
products[i]=products_below[i]*products_above[i];
}
If you need to be O(1) in space too you can do this (which is less clear IMHO)
int a[N] // This is the input
int products[N];
// Get the products below the current index
p=1;
for(int i=0;i<N;++i) {
products[i]=p;
p*=a[i];
}
// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i) {
products[i]*=p;
p*=a[i];
}
Here is a small recursive function (in C++) to do the modofication in place. It requires O(n) extra space (on stack) though. Assuming the array is in a and N holds the array length, we have
int multiply(int *a, int fwdProduct, int indx) {
int revProduct = 1;
if (indx < N) {
revProduct = multiply(a, fwdProduct*a[indx], indx+1);
int cur = a[indx];
a[indx] = fwdProduct * revProduct;
revProduct *= cur;
}
return revProduct;
}
Here's my attempt to solve it in Java. Apologies for the non-standard formatting, but the code has a lot of duplication, and this is the best I can do to make it readable.
import java.util.Arrays;
public class Products {
static int[] products(int... nums) {
final int N = nums.length;
int[] prods = new int[N];
Arrays.fill(prods, 1);
for (int
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;
}
public static void main(String[] args) {
System.out.println(
Arrays.toString(products(1, 2, 3, 4, 5))
); // prints "[120, 60, 40, 30, 24]"
}
}
The loop invariants are pi = nums[0] * nums[1] *.. nums[i-1]
and pj = nums[N-1] * nums[N-2] *.. nums[j+1]
. The i
part on the left is the "prefix" logic, and the j
part on the right is the "suffix" logic.
Jasmeet gave a (beautiful!) recursive solution; I've turned it into this (hideous!) Java one-liner. It does in-place modification, with O(N)
temporary space in the stack.
static int multiply(int[] nums, int p, int n) {
return (n == nums.length) ? 1
: nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
+ 0*(nums[n] *= p);
}
int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"
Translating Michael Anderson's solution into Haskell:
otherProducts xs = zipWith (*) below above
where below = scanl (*) 1 $ init xs
above = tail $ scanr (*) 1 xs
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With