Efficient Algorithm for subarray product
Can someone please Suggest an efficient algorithm O(nlogn) or O(n) for finding number of continuos subarray with product of elements divisible by 2 but not divisible by 4??
A bit off topic, but what do you gain by doing these questions?
(Responding to below: That didn't answer my question, but OK)
(Responding to below: That didn't answer my question, but OK)
Last edited on
I found it very new as I couldn't find any article on it on internet so I asked it here
Divide by 2 until the number is odd and that will tell you the power of 2 in the prime factorization. That will leave you with an array of exponents like [1, 0, 0, 2, 3, 1, 0]. Then you just need to find the clusters of contiguous zeroes that are next to a single 1.
Examples:
Matching: 2 0 0 0 1 2
Matching: 2 0 0 0 1 0 2
Matching: 2 0 0 0 1 1
Not matching: 2 0 0 0 0 2
Not matching: 2 0 0 0 0 3
Not matching: 3 0 0 0 0 3
Examples:
Matching: 2 0 0 0 1 2
Matching: 2 0 0 0 1 0 2
Matching: 2 0 0 0 1 1
Not matching: 2 0 0 0 0 2
Not matching: 2 0 0 0 0 3
Not matching: 3 0 0 0 0 3
Last edited on
Topic archived. No new replies allowed.