10^5 numbers each number 720720
3 Likes
We have to take the smaller one… what if i+1 - Cal(i)<dp[i-1]+1… then within the length of dp[i-1]+1 there is a number that is not coprime with the ith element … therefore we have to take the valid segment which is the smaller one
Hi, I tried to solve it using binary search the answer, but got TLE . Here is my solution. In every iteration of binary search, I am checking the subsets of expected length over the whole array, so I think the time complexity should be something like n*log(n)*alpha, where alpha will depend on the length of expected array in every iteration of binary search. Though I am no sure about it, can anyone help me with this ?
@l_returns ?? Apart from binary search, I had idea of using two pointers to find the product of segment in O(1) preprocessing and lcm of range in log(n) segment tree, but there also this alpha factor arrives which makes me of that complexity to pass.
I think you are doing O(n*length) with BS over length. Which makes it O(n^2) at least in worst case ( imagine whole array has LCM = multiplication).
What I suggest is O(n) for each length which makes it O(n*\log_2(n))
Use hashing + sliding window for each length in BS. Or use two pointers with this method.
How to check if a subarray has LCM=multiplication ?
If I am not wrong. LCM of n numbers is their multiplication If and only if GCD of each and every pair of numbers is 1.
Now use hashing and push all prime factors (along with their frequency (remember if number is 4 then don’t insert 2 twice, instead what we want is how many numbers are divisible by 2) ) of all numbers ( all numbers in subarray for which you want to check if it’s LCM=multiplication or not).
If frequency of all prime factors is 1 then it’s LCM= multiplication.
Use hashing to keep freq of freq as well to check if freq of all prime factors is 1 or not maybe.
That makes it O(n) for each length. Hence all over O(n*\log_2(n))
Correct me if I am wrong.
Isn’t your complexity same as well ? for every iteration in binary search, you are inserting,(or removing) n/k i.e. O(n) elements and checking for it. ?
Nope my complexity is O(1) per each subarray. I am removing one and adding one element.
Total n/k subarrays of size k for each BS.
Hence Time complexity n*log(n)
For the Sliding Window/Two Pointers approach, how do we move the left pointer if the current segment/window becomes invalid at some index? Say, for example, our Segment/Window was valid in [i…j] but now becomes invalid at j + 1, i.e. [i…j+1] is invalid. So, we need to move the left pointer from i to some index later. But what decisions do we make while moving the left pointer? I guess, we can keep moving the left pointer till gcd(ar[left_pointer], ar[j + 1]) != 1. Am I correct?
Please help @ssjgz @l_returns @admin5
Nope we move left pointer till kth position when all elements from gcd(k,j+1)==1 and gcd(k+1,j+1)==1 and … gcd(j,j+1) ==1
So for left pointer find leftmost position such that gcd ( of all elements from that position to jth pos, ar[j+1] ) should be one
PS : There can be multiple numbers having gcd(ar[left_pointer],ar[j+1])!=1
3 Likes
Does anyone have test cases for this question?
void solve()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans=-1;
int count=1;
int p=1;
int gcd=a[0];
while(p<n)
{
int k=GCD(max(gcd,a[p]),min(gcd,a[p]));
if(k==1)
{
count++;
gcd=gcd*a[p];
}
else
{
ans=max(ans,count);
count=1;
gcd=a[p];
}
p++;
}
ans=max(ans,count);
// cout<<ans<<endl;
p=n-2;
count=1;
gcd=a[n-1];
while(p>=0)
{
int k=GCD(max(a[p],gcd),min(a[p],gcd));
if(k==1)
{
count++;
gcd=gcd*a[p];
}
else
{
ans=max(ans,count);
count=1;
gcd=a[p];
}
p--;
}
ans=max(ans,count);
if(ans==1)
{
ans=-1;
}
cout<<ans<<"\n";
}
can anyone help me with this i have another approach can any one give me failing test case
Consider this input
Input
1
10
10 2 6 4 7 8 1 4 6 2
Expected Output
3
Your Output
2
1 Like
Thanks!!! will work on it.
Thanks for a really nice problem
Can someone please help me with my solution , I am getting TLE
Hey @phantom2411 
You have to precompute the factors of numbers till 10^6 as for the given constraint in worst case n can be 10^5 and for calculation of factor is approx 10^3 and test case are 50 it will exceed (8*10^8) which will give TLE.