Longest subarray
Time Limit: 2.0 s
Memory Limit: 256.0 MB
Description
Roy and Hridoy are good friends. They both love math. One day Roy preapared a problem to check his friend Hridoy's IQ level.
Problem is very simple, You are given an Array A[] of length \(N\). You need to find out the length of the longest subarray where the GCD of the subarray is greater than \(X\). Before you find longest subarray, you can do at most \(K\) operations (possibly zero) in the array,
in one operation :
- Select an index \(i\), \(1<=i<=N\) and increase \(i\)-th element by 1 (Ex. A[i]=A[i]+1)
Hridoy is busy with his University works and need your help to solve this problem.
Note: GCD means Greatest common divisor, GCD(2,4)=2, GCD(6,9,12)=3.
Input
First line takes two integer \(N,K\) : size of the array and maximum number of operations
second line takes \(N\) integers
\(1 <= N <= 10^5\)
\(1 <= K <= 10^7\)
\(1 <= X, Ai <= 100\)
Output
Print one integer : size of the maximum subarray
Sample
Input | Output |
---|---|
|
|
In the first testcase, Array A[]={2,4,7,9,12} and we can do at most K=2 operations.
First operation: select 3rd index and increase its value by 1. A[]={2,4,8,9,12};
Second operation: select 3rd index and increase its value by 1. A[]={2,4,9,9,12};
after that we can select the subarray from 3rd index to 5th index in which GCD(9,9,12)= 3 > X and the length of this subarray is 3 which is maximum.
Information
- ID
- 1043
- Difficulty
- 7
- Category
- (None)
- Tags
- (None)
- # Submissions
- 20
- Accepted
- 7
- Accepted Ratio
- 35%
- Uploaded By
Related
In following contests: