Split array as contagious Subarray having same product

I have been asked this question in telephonic round of <***>. I gave them the brute-force and Optimized solution and as a followup they added constraint which was what if the number is pretty large, so i gave them the string solution but they were not convinced as they were expecting nlogn solution. I tried this solution at home and tried with different approach but still didn’t get the correct approach.

The question is something like this.

Given an array of integers, return index K where K is

A[0] * A[1] * A[2] *… A[k] = A[k+1] * A[k+2] * A[k+3] *… A[N]

Note : If there are multiple possibilities return the first occurance

Example:

Given nums = [2, 2, 1, 2, 2], Because nums[0] * nums[1] = nums[2] * nums[3] * nums[4], return 1

Constraint :

1<=N<=10^5

1<=A[i]<=10^18

Well naive solution will be

1.Get product of arr[1]…arr[n]; 2. i = 0; Check if(arr[i] = total_product) else { arr[i] *= arr[i+1] total_product /= arr[i+1] }

But what about very large number like 10^18?

did they mention 10^18 themselves or jst said pretty large ?

For very large numbers, you store the prime factors and its power for each number, then compare.
Finding prime factors take O(logn) time.
Solution time complexity:- O(nlogn) :slight_smile:

How do you suppose we store the prime numbers? I’m new to this concept.
Do we build an array of prime numbers using Sieve of Erathosthenes and then go through the array until n/2? Then what? How is the information stored? How do we compare two numbers using their prime factors - wouldn’t that be far more complex than just directly comparing the numbers?

Can we not use BigInteger in this situation?

How could you find prime factor of 1e18 in logN time?
For getting efficiency you can use Pollard’s Rho algorithm, i think it will help. :grinning:

1 Like

Yep, we’ll use Pollard kaa algorithm only. I forgot its time complexity😅
Here is the implementation:- UVa 11476 - Factorizing Larget Integers | Morris' Blog
(On a side note:-You are my big inspiration…when I started competitive programming 5-6 months ago, I saw that you are (2nd)highest in the rank of problem-solving on Hackerearth. That , pushed me a lot, initially to solve problems. Feels great to converse with people who are my inspiration :slight_smile: )

To @kuelfdeez, even very large numbers have very small prime-factors,google it for proof, thats why we are storing each number as their prime factors.

1 Like