Minimum index Array Product

Given an array A(1 indexed based) of positive integers.For each element A[i] find the minimum index (say idx) such that the product of all the elements from index 1 to idx is divisible by A[i].where(1<=idx<=i).

constraints are: the number of elements of the array 1<=n<=10^5 and

1<=A[i]<=10^5.

For example let A[]={2,4,6,8}

The output should be {1,2,3,2}

I could only think of O(n^2) solution but that gives a T.L.E.

I also looked up to the code of successfully accepted solution but could not understand the logic.I only understood that it is first calculating the smallest prime factor using seive and then calculating the prime factors of each A[i] using its smallest prime factor.However I am not able to understand the later part of the solution.

Here is the code of one of the accepted solution.

int main() {

ll n,arr[500001],minP[500001];
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=2;i<=500000;i++){
minP[i]=i;
}
for(ll i=2;i*i<=500000;i++){
if(minP[i]==i){
for(ll j=i*i;j<=500000;j+=i){
minP[j]=min(minP[j],i);
}
}
}
vector<ll> v[500001];
for(int i=0;i<n;i++){
ll temp = arr[i],mx=0;
while(temp>1){
v[minP[temp]].push_back(i);
temp/=minP[temp];
}
temp = arr[i];
while(temp>1){
ll x=minP[temp],cnt=0;
while(temp%x==0){
temp/=x;
cnt++;
}
mx=max(mx,v[x][cnt-1]);
}
cout<<mx+1<<" ";
}


}

Also,Suggest me some relevant material to understand the underlying concept used above.

Here I have tried to implement the solution using binary search can anybody point the error as I am still getting the wrong answer upon submission.

 void Bsearch(int low,int high,int key,long long product[])
{

int ans;
int mid;
long long midVal;
while (low <= high)
{
mid = low + (high - low + 1) / 2;
midVal = product[mid];

if (midVal% key!=0)
{
low = mid + 1;
}
else if (midVal%key==0)
{
ans=mid;
high=mid-1;
}
}
cout<<ans+1<<" ";
}
int main()
{
int n;
cin>>n;
int arr[n];
long long product[n];
int i;
for(i=0;i<n;i++)
cin>>arr[i];
product[0]=arr[0];
for(i=1;i<n;i++)
product[i]=product[i-1]*arr[i];//prefix product array
for(i=0;i<n;i++)
{
int temp=arr[i];
Bsearch(0,n-1,temp,product);//Using binary search to find the minimum
index.
}
}

• Lesson: undocumented/uncommented code is of limited value even if apparently working. With a $\Theta(n²)$ solution too slow, what makes you assume there exists a $O(n)$ one? Sep 7, 2019 at 15:07

Here's a simple $$O(n \log n)$$ solution if multiplication and the modulus operator is always assumed to be $$O(1)$$ (which is a big assumption -- see the note at the end).

Create a new array, $$B$$, in which the first element is $$A[1]$$ and every future element at index $$i \in 2..n$$ is $$A[i] * B[i-1]$$. This gives you an array of all "partial products".

This array is nondecreasing, and $$B[j]$$'s factors are a superset or $$B[i]$$'s factors whenever $$i < j$$. Therefore, for any $$A[i]$$ (or even for every integer $$k$$), you can use binary search to find the smallest index $$i$$ for which $$k$$ divides $$A[1] * A[2] ... * A[i]$$. This takes $$O(\log n)$$ time per lookup, or $$O(n \ log n)$$ in total for all of $$A$$.

--

Regarding the initial assumption. As it turns out, assuming arithmetic operations can be done in constant time gives you a bit more power than what most people consider reasonable. For example, one can factor arbitrary integers in polynomial time under this assumption, by constructing pathologically large multiplications/divisions that let them "carpool" many different operations into one. Do you know which cost model we are operating under?

Pseudocode:

For 2 ≤ n ≤ 500,000 calculate minP [i] = smallest prime factor of n.

For each prime p, record the indices of every array element arr [i] that has p as a prime factor, recording an index multiple times if arr [i] has p^2, p^3 as a factor. (The code does this in a different order, iterating through the array elements first instead of the primes).

For each array element arr [i], and each prime factor p of arr [i]: Find which prime power p^k divides arr [i]. Consult the table created earlier to find at which point earlier array elements had the same number of prime factors p. And the largest of these values is the result we want.

Of course this doesn't run in O(n) where n is the number of array elements, but O ("total number of prime factors of all array elements"). There's also the minor problem that none of the arr[i] can have a prime factor > 500,000.

Material for the underlying concepts... A book about basic arithmetic? I don't think anything that the ancient greeks didn't know is required here.

Task 1: Create a data structure which given an integer N, can give you all primes from $$p ≤ N^{1/2}$$ in constant time each. This is quite easy: Given N, we calculate $$M = N^{1/2}$$, rounded down to the nearest integer. We keep an array of consecutive primes, starting with p = 2. If the highest of these primes is less than or equal to M, then we add primes until the array contains a prime greater than M. We then can just iterate through that array, until a prime greater than M is found.

Task 2: Create a data structure which given an integer N, produces the smallest prime factor of N: To do this, we create a hash table which maps integers N to their smallest prime factors. Given N, we look it up in the hash table, and return the result if N is present. Otherwise, we divide N by all prime numbers $$p ≤ N^{1/2}$$ until a divisor is found; if a divisor is found then we enter (N, divisor) into the hash table and return the divisor, otherwise N is prime and we enter (N, N) into the hash table.

Task 3: Have an algorithm that given an inteer N, determines all prime factors of N: We do this by looking up the smallest prime factor of N and dividing N by that factor, until N = 1.

Task 4: For each prime factor p contained in the array, have an array storing the first index i such that the product of a[0] to a[i] is divisible by $$p^k$$, for k = 1, 2, 3 etc. We do this by taking N = a[0], a[1] etc., determining all prime factors p, and adding i to the array for the prime p. (Note that if we have an upper limit for the size of array elements, we can determine the maximum possible power of any prime factor - for example, any 64 bit integer cannot have a factor $$p^k$$ with k > 63).

Task 5: For each array element, calculate all prime factors and their power, say $$p^k$$. Given the array of Task 4, find the smallest i such that the product a[0] to a[i] is divisible by $$p^k$$. The largest of these indexes is the result.

I think the worst case would be an array of n large different primes. If the primes are ≤ M, then determining this takes $$M^{1/2} / log M$$ steps, for total execution time of $$O (n * M^{1/2} / log M)$$.