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 18.5% which was shocking since this was one of the easiest problems in the contest.
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)
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 c++ which gives a good time complexity. After processing each 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 😃