given an array of integers(positive or negative), and two integers x, y. write a function that can find a subarray whose sum equals to x and product equals to y

Question

Pavel · Accepted Answer

Subarray suggests a consecutive array within the original array. Let's say this is the case.

Say you are given array A of length N. Create two more arrays:

1. B, whose n-th number is the sum of the first n numbers in A.
2. C, whose n-th number is the product of the first n numbers in A.

Say we are given subarray indices i  i in these collisions. We can find them in linear time by using a hashmap. Store the contents of B2 into a hashmap and iterate over B checking for collisions. Do the same thing with C and C2. The collisions will return pairs of indices (i, j). What do these mean? Collisions in B and B2 will produce sub-arrays that sum to x. Collisions in C and C2 will produce sub-arrays that multiply to y. All we do now is check for collisions between these. We can again use a hashmap.

All of the steps are linear so the algorithm is linear.

Anonymous · Answer

It's a recursive backtracking problem.  Create a helper method so you can keep a start index through the recursion.  Your base case is when you've reached the end of the array.  For each recursive call you have two options for the number at your start index, either chosen or not.  If chosen, manipulate x and y for the next recursive call, either subtracting or dividing (be sure to do modulo to ensure the number is a factor of y).  If not chosen, pass x and y back in as they are, but increment start.

The logical or of the chosen and not chosen paths should be the return value from the recursive helper method.  For the base case the return value is whether or not both x and y equal zero.

Anonymous · Answer

Slight correction to above -- you're not returning a boolean value, so when doing the logical or, return the array if it's true -- or null if false... same for comparisons of x and y to zero.

maddy · Answer

1. insert all array data into hash table.
2. Read first/next element of array. p = x- (first_num)
3. search p in hash table
4. If found return that. else go to step 2 till array exhausts.

do simillar step for finding dividend.

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches