World CodeSprint 13

Watson’s Love for Arrays

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.

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.

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.

Thanks for reading 😃

Related posts:

Employees are the backbone of every organisation and having motivated creative employees ensures enhanced performance and results! Learn how to make sure that your employees are always motivated and…

We look at a simple three step approach to improve your customer loyalty and create repeat purchases.

I am inspired by nature, fractals, and diverse sustainable practices. I am also a gardener planning and preparing for my first growing season in the Midwest. All of my ideas for this project center…