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?