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?
Take $$$log()$$$ for all values, and the product becomes sum.
Using logarithms introduces floating point computation, which is not the wisest thing to do.
Here's an alternative. By the fundamental theorem of arithmetic, you can always express the integers in your array as a product of primes. So you can store the prime factors of every element with their corresponding powers. Each integer (up to 10^18) should only have a small number of these prime factors because the product grows very quickly.
Now your problem just becomes comparing the prime factors and their powers. Don't forget to handle special cases such as -ve integers and 0.
I was really not satisfied by my idea, and thought about factorization, but I didn't know how to factorize a number reachs $$$10^{18}$$$. After your comment, I searched about it, and get this soln. which take $$$O(num^{0.25})$$$ to factorize an integer $$$num$$$, that is $$$O(10^4)$$$ in case of $$$num = 10^{18}$$$, which is not small enough when taking in consederation the size of the array in the problem in the blog. So, is there another effecient way to factorize, please? And thanks for letting me search more about factorization.
My bad. I didn't notice the array size upper bound. But theoretically, prime factorization can be done faster albeit with more conplex implementation (maybe quadratic sieve?). But I guess factorization might not be as fast as we would like it to be.
Not bad. Yeah, look at the first answer here, there are crazy things O_o
You can iterate through the array and remember actual product modulo some prime numbers. In each iteration you check if the conditions are met modulo these numbers. $$$O(nlog(nums))$$$ if you are keeping product of whole array and doing modular division, $$$O(n)$$$ if you calculate sufix products at the beginning.
Let's start a left pointer at the left end and a right pointer at the right end, and a score as a long double at 1. Whenever the score is >= 1 we'll increment the left pointer and divide. Otherwise we'll decrement the right pointer and multiply. Since we have all integer values in our input and nearly twice as many bits of precision than is needed to store any one value, even imprecise double math shouldn't be able to introduce a factor of two error into our calculation. Once we've met our pointers in the middle we can check against an epsilon for correctness.
Important distinction between my algorithm and your given is that the multiply/divide strategy guarantees that even with all numbers being 10^18 in size, we don't overflow the double/long double exponent.