# World CodeSprint 13

## Watson’s Love for Arrays

This was one of the problems of the recent hackerrank contest (** World CodeSprint 13**). It had a really low success rate

**which was shocking since this was one of the easiest problems in the contest.**

*18.5%*### Brute Force

Generate all sub-arrays and find the modular product and check if it’s equal to *k. *This is very straight forward way to solve the problem. And has a *O(n²) *complexity. n being the size of the array. *O(n²) *Since there are *n(n+1)/2 *sub-arrays.

### A better Solution

Alright, so we need something like *O(NlogN)* or *O(N)*. A lot of clues can be derived from this itself. Like the *N* factor would be from iterating over the array. It’s kinda obvious that to find the answer we need to iterate at least once through the array. Now that N’s out of the way. We are then allowed to do operations that take *O(1)* or *O(logN)* time to solve the problem at each index *i (1≤i≤N)*

#### Observations

If lets say our array size was some *x *now we would like to make the array size *x+1 *by appending an element to the end of the array. *How many new sub-arrays are added?*

It’s *x+1 . *Try a few examples you’ll know why. So for each new element added the sub-array that include this element can be from *indices [i:x+1] (i to x+1) *where *i* is in range*(1≤i≤x+1). *So the problem now reduces to, at each index k we need to find number of points *i where (1≤i≤N) *such that product from *(i to k) mod m *gives *k *. We need to find the count of these points *i *in *O(logN) or O(1) *time.

#### Find Product from *(i to j)*

How to do this efficiently. Using prefix products (for more on prefix products click *here**) . *If you know the product till 0 to i-1 we can easily calculate for 0 to i. Therefore product from i to j is *(product_till[i]/product_till[j-1]) *memoize these. Note that we need to find modular product

**Find the count**

Now we need to count number of points *i* such that product from *(j to i) *is *k where j≤i. *If they are equal to k then sub-array from *[j+1:i]* will have product *k*

Division is not always good idea. So lets take the denominator to the other side.

So the problem now reduces to counting the number of elements before *i *in the prefix product array whose value equals to *k*productTill[j] (*count_of(*k*productTill[j]) ).*

*Another *way would be to directly find such value productTill[j] which is *count_of(productTill[i]*modinverse(k)) *give it some thought 😉.

count_of(*k*productTill[j]) *can be easily achieved through ** unordered_map** in

**which gives a good time complexity. After processing each**

*c++**i*we insert/increment

*productTill[i]*k*count into the map so that future indices can make use of the result. Print the final count which is the answer to the problem.

Here is my *CODE**. *I have not discussed about taking mod and other implementation details here to keep the blog simple as possible. If you have any queries please make a comment.

Thanks for reading 😃