 # KSUB - Editorial

Author: Vibhu Garg
Testers: Utkarsh Gupta, Jatin Garg
Editorialist: Nishank Suresh

1604

# PREREQUISITES:

Familiarity with gcd

# PROBLEM:

You have an array A and an integer K. Let G = \gcd(A).
Find out whether there exist K disjoint non-empty subarrays in A with gcd g_1, \ldots, g_K such that \frac{g_1 + g_2 + \ldots + g_K}{K} = G.

# EXPLANATION:

First, note that the gcd of any subarray of A will certainly be at least G, since G divides every element of A.
So, each g_i \geq G, which means the only way their average can equal G is if each g_i itself equals G.

So, we need to find if K disjoint subarrays in A have gcd G.
Note that since G divides every element of A, if we have a subarray whose gcd is G, extending this subarray to the right or left will still leave its gcd as G.

In particular, if a solution exists, then there will always exist a solution that covers the full array.
This gives us a simple algorithm to check:

• While the array is not empty, find the smallest prefix of the array with gcd G. If no such prefix exists, stop.
• This prefix (if found) will form one subarray in the answer. Remove this prefix and do the same to the remaining array.

The number of times we successfully performed the operation equals the maximum number of disjoint subarrays with gcd G that can be obtained. Check if this number is \geq K or not.

This can be implemented quite easily:

• Keep a variable denoting the current gcd, say g. Initially, g = 0.
• For each i from 1 to N:
• Set g := \gcd(g, A_i).
• If g \gt G, continue on
• If g = G, increase the answer by 1 and reset g to 0.

# TIME COMPLEXITY

\mathcal{O}(N\log (maxA)) per test case.

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;

int gcd (int a, int b) {
if (b == 0)
return a;
else
return gcd (b, a % b);
}

int main(){

int t;
cin >> t;

while(t--){

int n, k;
cin >> n >> k;

vector <int> v(n);
int G = 0;

for(int i = 0; i < n; i++){
cin >> v[i];
G = gcd(G, v[i]);
}

int currG = 0, count = 0;

for(int i = 0; i < n; i++){
currG = gcd(currG, v[i]);
if(currG == G){
count++;
currG = 0;
}
if(count == k) break;
}

if(count == k){
cout << "YES\n";
}
else{
cout << "NO\n";
}

}
return 0;
}

Editorialist's code (Python)
from math import gcd
from functools import reduce
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
G = reduce(gcd, a)
cur = taken = 0
for i in range(n):
cur = gcd(cur, a[i])
if cur == G:
cur = 0
taken += 1
print('Yes' if taken >= k else 'No')


Hi,

I think this is an incomplete solution to the problem as it wouldn’t work for a test case such as
4 2
2 2 3 3

Because G for this test case is 1 and this algorithm above will take [2,2,3] as a valid subarray. however  will be left and will result in 3 as it’s gcd. this will result in 1 valid subarray which will result in a NO. however, 2 subarrays are possible such as [2,3], [2,3] both with 1 gcd. Therefore the answer should be Yes.

1 Like

subarrays are contiguous, so it’s impossible, do you mean subsequence??

1 Like

Hello,

1
4 2
4 10 6 10

My submission in this testcase gives “NO” as output but I think it should be “YES”
Still my code got AC. Why?

i may be wrong but, just because it is mentioned “subarray” i believe this code works, bcz in case of subsequences it will always work?