This is an interview question.
I have a list of numbers, where list size is n, find maximum subarray length with Greatest Common Divisor (GCD) greater than 1, find the minimum possible value as result.
Input to the program also contains maxChange which indicates maximum changes allowed on input list, where each change indicates changing any one value in the list to any other value.
Example list=[2, 2, 4, 9, 6] maxChange = 1
Some possible changes are :
Change the first element to 3.so list = [3, 2, 4, 9, 6]. The length of the longest subarray with a GCD greater than 1 is 2 for the subarrays [2, 4] and [9, 6].
Change the third element of the list to 5. The list becomes = [2, 2, 5, 9, 6]. In this case, the length of the longest subarray with a GCD greater than 1 is 2 for the subarrays [2,2] and [9, 6].
Since no operation can reduce the maximum length of any subarray with a GCD greater than 1 to less than 2, solution is 2.
Examples:
list=[5,10,20,10,15,5] maxChange = 2
Answer = 2
Explanation Here are some possible changes to achieve the least
First Change: change third element of the input to 2 and the fourth element to 3, so the list becomes [5, 10, 2, 3, 15, 5]. In this case, the maximum length of a subarray with a GCD greater than 1 is 2. This applies to several subarrays: [5, 10], [10,2], [3,15], [15,5]
Second Change: • change the first element of the list to 7 and the fourth element to 9, so the updated list becomes [7, 10, 20, 9, 15, 5]. • Here as well, the maximum length of a subarray with a GCD greater than 1 is 2, for the following [10, 20], [15,5]
Hence, after making the changes, the least possible answer is 2.
Example:
list = [4,2,4]
maxChange = 1
Answer = 1
Explanation
Currently, the list has a GCD of 2 and a length of 3, but the optimal length is 1. The only way to achieve the optimal length is to change the second element to a value that has a GCD of 1 with 4. For example, change the key to [4, 3, 4]. In this case, the subarrays with a GCD greater than 1 are: [4], [3], [4] Since the maximum length of these subarrays is 1, the least possible result is 1.
other examples :
list = [5,6,3,6,12]
maxChange = 1
Answer: 2
list = [158260522]
maxChange = 0
Answer = 1
constraints:
1 <= n <= 10^5
0 <= maxChange <= n
1 <= list[i] <= 10^9
I am totally lost how to solve this problem, what is the correct way to solve this.
This is pretty tough for an interview question, but you can solve it in O(n log n)-ish time by reducing it to an easier problem:
Given an array of positive integers
A, and a maximum subarray lengthL, how many elements do you have to change to ensure that there are no subarrays of length >Lwith GCD > 1.
If you can solve this problem, then you can do a binary search over array lengths to find the smallest L for which the number of required changes <= maxChange, and that is the answer to the hard problem. If you can solve the easier problem in linear time, then the original problem takes O(n log n).
Here's how to solve the easier problem:
Given L, the maximum allowed subarray length, M = L+1, is the minimum disallowed subarray length. All subarrays of length M need to be broken if they have a common GCD > 1
Given M, consider every Mth element of A to be "marked", so there is a mark at A[0], A[M], A[2M, etc... Notice that every subarray of length M overlaps exactly one mark.
For each mark, there are exactly M overlapping subarrays of length M, or fewer for the first and maybe last marks. Starting at the first mark, find the first invalid M-length subarray that overlaps the mark. If there is one, change its last element to 1. Since the new 1 will be on or after the mark, it is now guaranteed that there are no more invalid subarrays that overlap the mark.
Proceed to perform the same operation for every mark.
It's reasonably easy to prove that this algorithm produces the fewest possible number of changes that break all invalid subarrays.
Finally, the remaining question is how to find the first invalid subarray that overlaps a mark.
First, note down the cumulative GCDs, starting at the mark and working backwards to the previous mark, and the cumulative GCDs starting at the mark and working forwards to the next mark. For M=3, for example, we could have:
MARK
v
A = ... 20, 27, 12, 18, 9
GCDS = ... 1 3 12, 6, 3
| |
GCD = 3
FIXED = ...20, 27, 12, 1, 9
Now you can easily find the GCD of any M-length subarray that overlaps the mark by taking the GCD of the cumulative GCDs you noted down at its first and last elements.
Putting all this together gets you the final algorithm that takes at most O(n log n) * GCD_TIME. Whether or not you consider GCD_TIME to be a constant is up to you.
Here's an implementation in Java:
public class BreakGCD {
// Make at most maxChanges changes to minimize the length of the longest
// subarray with total GCD > 1.
// return the minimal longest length
public static int getMinAchievableMaxGcdLength(int[] array, int maxChanges) {
if (array.length < 1) {
return 0;
}
int minResult = 0;
int maxResult = array.length / (maxChanges+1);
while (minResult < maxResult) {
int test = minResult + ((maxResult - minResult)>>1);
if (getMinChangesForMaxGcdLength(array, test) > maxChanges) {
// test is too low
minResult = test+1;
} else {
// test is high enough
maxResult = test;
}
}
// now minResult == maxResult == answer
return minResult;
}
static int getMinChangesForMaxGcdLength(int[] array, int testLength) {
int changeCount = 0;
final int invalidLen = testLength+1;
int[] gcds = new int[array.length];
//we'll use this to keep track of the first place an invalid array could start,
//so that we don't actually have to modify array
int startPos = 0;
for (int mark = 0; mark < array.length; mark += invalidLen) {
gcds[mark] = array[mark];
// calculate cumulative GCDs away from mark
for (int d=1; d<=testLength; ++d) {
if (mark+d < array.length) {
gcds[mark+d] = gcd(array[mark+d], gcds[mark+d-1]);
}
if (mark-d >= startPos) {
gcds[mark-d] = gcd(array[mark-d], gcds[mark-d+1]);
}
}
for (int i = Math.max(startPos, mark-testLength); i <= mark && i+testLength < array.length; ++i) {
if (gcd(gcds[i], gcds[i+testLength]) > 1) {
// found invalid array
++changeCount;
startPos = i+testLength+1;
break;
}
}
}
return changeCount;
}
static int gcd(int a, int b) {
if (a<=0 || b<=0) {
throw new IllegalArgumentException("GCD arguments must be > 0");
}
for (;;) {
a%=b;
if (a==0) {
return b;
}
b%=a;
if (b==0) {
return a;
}
}
}
public static void main(String[] argv) {
int[] test = new int[] {5,10,20,10,15,5};
System.out.println(getMinAchievableMaxGcdLength(test, 2));
}
}