Ehab loves number theory, but for some reason he hates the number x. Given an array a,…
- User
Ehab loves number theory, but for some reason he hates the number x. Given an array a, find the length of its longest subarray such that the sum of its elements isn't divisible by x, or determine that such subarray doesn't exist.
An array a is a subarray of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Input
The first line contains an integer t (1 ≤ t ≤ 5) — the number of test cases you need to solve. The description of the test cases follows.
The first line of each test case contains 2 integers n and x (1 ≤ n ≤ 10^5, 1 ≤ x ≤ 10^4) — the number of elements in the array a and the number that Ehab hates.
The second line contains n space-separated integers a_1, a_2, …, a_{n} (0 ≤ a_i ≤ 10^4) — the elements of the array a.
Output
For each testcase, print the length of the longest subarray whose sum isn't divisible by x. If there's no such subarray, print -1.
Example
Input
3 3 3 1 2 3 3 4 1 2 3 2 2 0 6
Output
2 3 -1
Note
In the first test case, the subarray [2,3] has sum of elements 5, which isn't divisible by 3.
In the second test case, the sum of elements of the whole array is 6, which isn't divisible by 4.
In the third test case, all subarrays have an even sum, so the answer is -1.
Assistant
We need to interpret the problem: "Ehab loves number theory, but for some reason he hates the number x. Given an array a, find the length of its longest subarray such that the sum of its elements isn't divisible by x, or determine that such subarray doesn't exist."
We are given t test cases. Each test case: n, x, and array a of length n. We need to output length of longest subarray (contiguous) whose sum is NOT divisible by x. If no such subarray exists, output -1.
Constraints: n up to 1e5 per test, t up to 5, sum n probably up to 5e5? Usually. x up to 1e4. a_i up to 1e4.
We need an efficient solution per test case: O(n) or O(n log something).
We need to find the maximum length L such that there exists a subarray of length L with sum % x != 0. If all subarrays have sum divisible by x, answer -1.
Observations: If total sum of entire array is not divisible by x, then answer is n (the whole array works). Otherwise, total sum % x == 0. Then we need to find some subarray that removes some prefix and/or suffix to get a sum not divisible by x. We can consider the idea that if we remove a prefix whose sum mod x is non-zero, then the remaining suffix sum = total - prefix_sum. Since total mod x =0, suffix mod x = -prefix mod x (mod x). So suffix mod x != 0 if prefix mod x != 0. Similarly, removing a suffix yields a prefix with sum mod x = total - suffix mod x? Actually if total sum ≡ 0 mod x, then any subarray that is a suffix (from i to n) has sum = total - prefix_{i-1} sum. So its mod = -prefix_{i-1} mod x. So if prefix_{i-1} mod x != 0, the suffix is not divisible. So the longest subarray not divisible by x would either be the whole array if its sum not divisible; else, we can consider removing either a prefix or a suffix such that the remainder is not divisible. The longest such subarray would be either the whole array minus a prefix that makes remainder non-zero, or minus a suffix, whichever yields longer length. So we need to find the smallest prefix (by length) whose sum mod x != 0, and then the remaining suffix length = n - prefix_len would be candidate. Similarly, find the smallest suffix (by length) whose sum mod x != 0, then prefix length = n - suffix_len is candidate. The answer would be max of those two, if they exist, else -1.
But is that always optimal? Consider a subarray that is not a prefix or suffix but somewhere in the middle. For example, we could remove both a prefix and a suffix, leaving a middle subarray. The length of that middle subarray = n - len(prefix) - len(suffix). Its sum = total - prefix_sum - suffix_sum. total mod x =0, so middle mod x = - (prefix_sum + suffix_sum) mod x. We want middle mod x != 0. Could such a middle subarray be longer than both n - smallest_prefix_nonzero and n - smallest_suffix_nonzero? Let's analyze.
Suppose we have total sum % x = 0. If there exists at least one element a_i such that a_i % x != 0, then we could take subarray of length 1 containing that element (since a_i not divisible by x), answer at least 1. But we want maximum length.
We can think in terms of prefix sums: Let P[0] = 0, P[i] = sum of first i elements mod x. Then sum of subarray [l+1, r] = P[r] - P[l] mod x. We want subarray with non-zero mod. So we need P[r] != P[l] mod x. So we want the longest distance between two indices where prefix sums are different mod x. Because if P[r] ≡ P[l] (mod x), then the subarray sum is divisible by x; else it is not.
Thus the problem reduces to: Given an array of prefix sums modulo x (including P[0]=0), find the maximum distance (r - l) such that P[r] != P[l] (mod x). If all P[i] are equal (i.e., same modulo), then any subarray sum is divisible by x (since P[r] == P[l] always), so answer -1. Otherwise, answer = max_{i,j: P[i]!=P[j]} (j - i). Since we consider subarray from i+1 to j.
This is a classic problem: longest subarray with sum not divisible by x. We can compute prefix sums mod x and then record the first and last occurrence of each residue. Then the maximum length would be max of (last occurrence of residue r - first occurrence of residue s) for residues r != s? But careful: We need indices i and j with different residues. The maximum distance could be between some first occurrence of some residue and last occurrence of a different residue. Since we want j - i such that P[i] != P[j]. That is essentially: If we have residues with multiple indices, we can consider the earliest occurrence of each residue and the latest occurrence of each residue. Then the maximum distance could be either:
-
Last occurrence of some residue r minus first occurrence of a residue s != r.
-
Also maybe last occurrence of r minus first occurrence of r would be a candidate if we consider i and j same residue? No, that yields P[i]=P[j], so subarray sum divisible, not wanted. So we ignore same residues.
Thus we need to maximize over pairs of residues where we take the smallest index from one residue and the largest index from another residue.
But is there any better way? Since we only have up to x residues, x up to 1e4, but n up to 1e5. That's manageable: we can track first and last occurrence for each residue. Then iterate over all pairs of residues (r != s) compute last[s] - first[r] and last[r] - first[s], take max. That is O(x^2) which could be up to 1e8 per test case if x=1e4, t=5 => 5e8 maybe borderline but could be okay in C++ with optimization? But we can do smarter: To find max distance between two different residues, we can consider the earliest index among all residues (global min index) and the latest index among all residues (global max index). If they have different residues, then answer = max_index - min_index. However, if the global min and max indices have the same residue, then we might need to consider second best. More generally, the max distance can be obtained by either taking the latest occurrence of any residue and the earliest occurrence of a residue different from that, or the earliest occurrence of any residue and the latest occurrence of a residue different from that.
So we can compute for each residue: first occurrence (min index) and last occurrence (max index). Then we can compute global_min_index = min over residues of first[r] (or maybe over all indices? Actually we want earliest index among all prefix sum indices, that is 0? Wait indices: P[0] = 0 is index 0. So earliest index is 0. But note that P[0] = 0 is included. So the set of residues includes 0 at index 0. So the earliest index is 0 (residue 0). The latest index is n (since P[n] is total sum mod x). So if 0 and some other residue differ? But we need to consider that P[0] is included. So indeed indices range from 0 to n.
Now if we take i=0 and j=n, if P[0] != P[n], then the whole array sum is not divisible by x, answer n. So the problem reduces to what we described: if total sum mod x != 0 then answer n.
If total sum mod x = 0, then P[0] = 0 and P[n] = 0, so they have same residue. But maybe there is some i such that P[i] != 0. Then we can take i=0 with some j where P[j] != 0, that gives length = j - 0 = j. Or i with P[i] != 0 and j = n gives length = n - i. So these correspond to removing a prefix (i > 0) or suffix (j < n). So the max length in that case is max of (max_{j: P[j]!=0} j) and (max_{i: P[i]!=0} (n - i)). That's essentially: longest prefix ending at j with sum not divisible? Wait: For i=0, subarray [1..j] sum = P[j] - P[0] = P[j] mod x, we need P[j] != 0. So the longest prefix that has sum not divisible by x is max j with P[j]!=0. Similarly, for suffix starting at i+1 to n, subarray sum = P[n] - P[i] = -P[i] mod x, we need P[i] != 0, so length = n - i. So the longest suffix that has sum not divisible is max (n - i) for i with P[i]!=0. So the answer would be max of these two. That matches our earlier idea: remove smallest prefix with sum%x !=0? Actually longest suffix = n - (minimal i such that P[i]!=0)? Let's examine: For suffix starting at i+1, length = n - i. To maximize n - i, we need i as small as possible. So we want the smallest i (>=0) such that P[i] != 0? But i=0 gives P[0]=0 (residue 0) so not !=0. So the smallest i where P[i] !=0 gives the longest suffix. Similarly, for prefix ending at j, length = j; we want largest j where P[j]!=0? Actually for prefix from 1 to j, length = j. So we need j as large as possible such that P[j] != 0. That's the maximum index with residue !=0. So answer = max( max_{j: P[j]!=0} j, n - min_{i: P[i]!=0} i ). That's equivalent to earlier suffix: the smallest i with P[i]!=0 yields longest suffix length = n - i; the largest j with P[j]!=0 yields longest prefix length = j. Both are candidate.
But could there be a longer subarray that is neither a prefix nor a suffix? That would involve both i>0 and j<n. Then length = j - i. We want P[i] != P[j]. Could this length be larger than both max_j and n - min_i? Let's test with an example.
Suppose n=5, residues at indices 0..5: P[0]=0, P[1]=0, P[2]=1, P[3]=0, P[4]=0, P[5]=0. total sum mod x =0 (since P[5]=0). Then min_i with residue !=0 is i=2, max_j with residue !=0 is j=2 (only index 2). So max prefix length = 2 (subarray 1..2), suffix length = n - i = 5-2=3 (subarray 3..5? Actually starting at i+1=3 to 5, length 3). So max is 3. Now consider a middle subarray: i=1 (P[1]=0) and j=2 (P[2]=1) -> P[i]!=P[j], length = j-i = 1. i=2 and j=3: P[2]=1, P[3]=0, length =1. i=1 and j=3: both 0 -> not allowed. i=0 and j=2 -> length 2 (prefix). i=2 and j=5 -> length 3 (suffix). So max is 3 indeed. So prefix/suffix covers all possibilities.
But is there a scenario where the longest distance between different residues is not involving index 0 or n, and is longer than both max_j (with residue !=0) and n - min_i (with residue !=0)? Let's construct: Suppose residues: index0:0, index1:1, index2:2, index3:0, index4:1, index5:0? Wait we need total sum =0 mod x so P[n]=0. But let's try n=6. Let x be large enough that residues are just numbers. For instance, x=10 (but we care only modulo). Suppose P[0]=0, P[1]=1, P[2]=2, P[3]=3, P[4]=4, P[5]=5, P[6]=0 (total sum mod 10 =0). So residues: indices 0..6: 0,1,2,3,4,5,0. min_i with residue !=0 is i=1, max_j with residue !=0 is j=5. So max prefix length =5, suffix length = n - min_i =6-1=5. So max=5. Now consider a middle subarray: i=0 (0) and j=5 (5) -> length 5 (prefix). i=1 (1) and j=6 (0) -> length 5 (suffix). i=0 and j=6: same residue (0) not allowed. i=2 and j=5: both? 2 vs 5 allowed, length 3. So max still 5.
Now suppose we have residues: index0:0, index1:0, index2:1, index3:0, index4:2, index5:0, index6:0, total sum =0. min_i !=0 =2, max_j !=0 =4. prefix max =4? Actually max_j !=0 is index4, j=4 -> length 4 (subarray 1..4). suffix max = n - min_i =6-2=4. So both =4. Could there be a subarray from i=1 (0) to j=4 (2) -> length 3? Or i=2 (1) to j=5 (0) length 3? So max=4.
Now consider if there is a residue that appears at both early and late positions but we need different residues, maybe the longest distance is between an early index of residue A and a late index of residue B, where A != B. That distance could be larger than both max_j (largest index with residue !=0) and n - min_i (smallest index with residue !=0) if the largest index with residue !=0 is not the global maximum index (which is n, but n has residue 0 if total sum divisible) and the smallest index with residue !=0 is not global minimum index (0). However, note that the global minimum index is 0 (residue 0) and global maximum index is n (residue 0 if total sum divisible). Since 0 and n are both residue 0, they are same residue, so cannot use them together. But we can use one of them with a different residue. For example, consider using i=0 with j = last occurrence of some residue r != 0: length = j. That is exactly max_j for r != 0? Since j is the maximum index with any residue !=0? Actually j is the largest index among all residues !=0. That is max_j. Similarly, i = first occurrence of a residue r != 0, j = n: length = n - i, which is n - min_i among residues !=0? Actually i is the smallest index with residue !=0, so length = n - i. So these two are exactly the candidates.
What about using i = first occurrence of some residue r1 and j = last occurrence of residue r2, with r1 != r2, where r1 could be 0? But 0's first occurrence is index 0 (if we consider P[0]=0). That is the smallest index overall. And r2's last occurrence could be some index maybe > the largest index with residue !=0? But the largest index overall is n, which has residue 0. So if we use i=0 (residue 0) and j = last occurrence of residue 0? That's not allowed because same residue. So we need r2 != 0. The largest j with residue !=0 is max_j. So i=0 with j = max_j yields length = max_j.
If we use i = first occurrence of residue r1 !=0, and j = n (residue 0), yields length = n - first occurrence of r1. This is n - min_i.
Now, could there be a pair where i is not 0, and j is not n, but i is the first occurrence of some residue r1 and j is the last occurrence of some residue r2, with r1 != r2, and both r1 and r2 are non-zero, such that j - i > max(max_j, n - min_i)? Since max_j is the maximum j among all non-zero residues, any j in such pair is ≤ max_j. And i ≥ min_i (the smallest index among all non-zero residues). So j - i ≤ max_j - min_i (since i≥min_i and j≤max_j). But is it possible that max_j - min_i > max(max_j, n - min_i)? Let's compare:
- max_j - min_i vs max_j: Since min_i >0 (as min_i is at least 1? Actually could be 0? Not for non-zero residues because residue 0 at index0, but min_i for non-zero residues is >0). So max_j - min_i < max_j if min_i >0. So it's less than max_j.
- max_j - min_i vs n - min_i: Since max_j ≤ n (strictly less than n if total sum divisible because P[n]=0, and max_j is index of non-zero, so max_j < n? Could be n if total sum not divisible, but in this case total sum divisible, so max_j ≤ n-1). So max_j - min_i ≤ (n-1) - min_i = n - min_i - 1, which is less than n - min_i. So indeed max_j - min_i < n - min_i.
Thus any pair with both residues non-zero yields j - i ≤ max_j - min_i, which is strictly less than both max_j and n - min_i (since min_i>0 and max_j<n). Therefore the maximum length is indeed max(max_j, n - min_i). So the earlier reasoning is correct: when total sum % x == 0, the longest subarray with non-divisible sum is either the longest prefix ending at a point where prefix sum !=0, or the longest suffix starting from a point where prefix sum (before start) !=0. So we only need to compute the smallest index i > 0 (since i=0 has residue 0) such that P[i] % x != 0? Actually we need smallest i with residue !=0? That gives longest suffix. But careful: For suffix starting at position i+1, we need prefix sum at i (before start) not divisible by x, i.e., P[i] != 0. So smallest i (where P[i] != 0) yields largest suffix length = n - i. That's correct.
Similarly, we need largest j (where P[j] != 0) yields longest prefix length = j.
But what if there is no i with P[i] != 0? That would mean all prefix sums are 0 mod x, which implies every a_i is divisible by x? Actually if all prefix sums are 0 mod x, then sum of each prefix is divisible by x, including a_1 = P[1] - P[0] =0 mod x, so each a_i divisible by x. Then any subarray sum is sum of some a_i's, each divisible by x, so any subarray sum divisible by x. So answer -1. So indeed if there is at least one index with non-zero residue, answer exists and is max of those two.
Thus algorithm for each test case:
- Read n, x.
- Compute total sum of array (maybe as we compute prefix sums mod x).
- But we don't need total sum separately; we can compute prefix sum mod x as we go.
- Keep track of first index where prefix_mod != 0 (i.e., the smallest i such that P[i] != 0, i from 1 to n? Actually i=0 is P[0]=0 always, so start from 1). Also keep track of last index where prefix_mod != 0.
- After processing all elements, we have P[n] (total_mod). If total_mod != 0: answer = n.
- Else: if we never encountered a non-zero prefix_mod (i.e., first index not set), answer = -1.
- Else: answer = max( last_nonzero_index, n - first_nonzero_index ).
But is this always correct? Let's test with examples.
Example 1: n=3, x=3, a=[1,2,3]. Compute prefix_mods: P[0]=0. a1=1 => P[1]=1 mod 3 =1 (non-zero) first=1, last=1. a2=2 => P[2]= (1+2)=3 mod3=0 (not non-zero). a3=3 => P[3]= (0+3)=3 mod3=0. total_mod =0. first_nonzero=1, last_nonzero=1. answer = max(1, 3-1=2) =2. Output 2. matches.
Example 2: n=3, x=4, a=[1,2,3]. total sum =6 mod4=2 !=0 => answer =3. matches.
Example 3: n=2, x=2, a=[0,6]. total sum =6 mod2=0. prefix_mods: P0=0, P1=0 mod2=0, P2=0 mod2=0. No non-zero prefix_mod. answer -1. matches.
Another test: n=5, x=5, a=[5,5,5,5,5]. total_mod=0, all prefix_mods 0 => answer -1. Correct.
Another test: n=5, x=5, a=[1,4,5,0,0]. total sum=10 mod5=0. prefix_mods: P0=0, P1=1 (non-zero: first=1,last=1), P2=1+4=5 mod5=0, P3=0+5=0, P4=0+0=0, P5=0+0=0. So first=1, last=1. answer = max(1,5-1=4)=4. Let's check: longest subarray not divisible by 5? The suffix from index2 to 5 (since first=1, start at i+1=2) length 4, sum = 4+5+0+0=9 mod5=4 not divisible. Or suffix from index1? But i=0 not allowed because P[0]=0, so suffix length 5 sum=10 divisible. So longest is 4. Good.
Consider scenario: first_nonzero at index 2, last_nonzero at index 4. n=6. total_mod=0. Then answer = max(4, 6-2=4) =4. Could there be a longer subarray of length 5? Possibly if we use i=0 with j=4? That's prefix length 4 (since j=4) not 5. i=2 with j=6 (suffix length 4). So 4 seems max. So fine.
But is there any case where the longest subarray is not captured by this approach? Let's think about possibility where the total_mod != 0, answer n, that's fine. When total_mod =0, we argue longest is max( longest prefix with non-zero sum, longest suffix with non-zero sum). However, consider a subarray that excludes both ends, but is longer than both candidate prefix and suffix? Since prefix candidate length = j where j is largest index with P[j]!=0. That j could be less than n. Suffix candidate length = n - i where i is smallest index with P[i]!=0. Could there be a case where the maximum j - i for some i and j with P[i]!=P[j] is greater than both j_max and n - i_min? Let's try to find a counterexample.
We need j - i > max(j_max, n - i_min). Since j_max is the maximum j with any non-zero residue, and i_min is the minimum i with any non-zero residue. For a middle subarray, i > i_min and j < j_max generally, so j - i < j_max - i_min. So the inequality j - i > max(j_max, n - i_min) would require that either j_max - i_min > j_max (impossible because i_min > 0) or j_max - i_min > n - i_min (impossible because j_max ≤ n). So indeed impossible. Therefore the maximum is achieved by using one of the ends (i=0 or j=n). So approach stands.
But we must be careful: What about using i=0 and j= some index where P[j] != P[0]? That is prefix candidate; we already considered j_max (largest j with P[j] != 0). But what if P[0] = 0, and there exists some residue r !=0 whose last occurrence is at index j, but also there might be a larger index j' where residue is 0? But j' would be n or some other index with 0, but that would yield P[j'] =0 = P[0], so not allowed. So the only allowed with i=0 is j with residue !=0. So the maximum j such that P[j]!=0 is indeed the best prefix candidate.
Similarly for j=n, i must have P[i] != P[n] =0, so i must have residue !=0. To maximize n - i, we minimize i among those with residue !=0. So we need smallest i with P[i]!=0. That's i_min. So suffix candidate is n - i_min.
Thus the algorithm is sound.
Edge cases: If total_mod !=0, answer = n. But could there be a longer subarray than n? No, maximum is n.
If total_mod =0 and there is at least one non-zero prefix_mod, answer = max(last_nonzero, n - first_nonzero). But ensure that first_nonzero is defined. Also note that the prefix length candidate is last_nonzero, which is an index j (1-indexed? Actually prefix length = j because subarray from 1..j). Similarly suffix length = n - i, where i is the index of prefix_mod before start; if i=first_nonzero, then subarray is from i+1 to n, length = n - i. So yes.
But we need to consider the possibility that the longest subarray might actually be of length n-1? That is captured: if first_nonzero = 1 then suffix length = n-1; if last_nonzero = n-1 then prefix length = n-1; whichever larger. So okay.
Now, there is nuance: What about the possibility that the array has zeros? The prefix sum mod x can be zero multiple times. That's fine.
One more nuance: The array elements a_i can be 0 and up to 10^4, but x up to 10^4. We compute mod, okay.
Thus algorithm per test case:
- Initialize first_nonzero = -1, last_nonzero = -1.
- prefix_mod = 0.
- Loop i from 1 to n:
- read a_i (or use array)
- prefix_mod = (prefix_mod + a_i) % x
- if prefix_mod != 0: if first_nonzero == -1: first_nonzero = i last_nonzero = i
- After loop, total_mod = prefix_mod.
- If total_mod != 0: print n
- Else if first_nonzero == -1: print -1
- Else: print max(last_nonzero, n - first_nonzero)
Check example: n=3, x=3, a=1,2,3 -> first=1, last=1, total_mod=0, answer max(1,3-1=2)=2. ok.
Test: n=5, x=5, a=1,4,5,0,0 -> first=1, last=1, total_mod=0, answer max(1,5-1=4)=4. ok.
Test: n=5, x=5, a=5,1,4,0,0? Compute: P[0]=0. a1=5 => P[1]=0 -> not non-zero. a2=1 => P[2]=1 (first=2,last=2). a3=4 => P[3]= (1+4)=5 mod5=0. a4=0 =>0; a5=0=>0. total_mod=0. first=2,last=2. answer = max(2, 5-2=3)=3. Check: suffix from index3 to 5 sum =4+0+0=4 mod5=4 not divisible, length 3. Prefix of length 2 sum=5+1=6 mod5=1 not divisible, length 2. So answer 3. Good.
Test: n=5, x=5, a=2,3,5,0,0. total=10 mod5=0. P1=2 (first=1,last=1), P2=2+3=5 mod5=0, P3=0+5=0, P4=0, P5=0. first=1,last=1. answer max(1,4)=4. suffix from index2 to5 sum=3+5+0+0=8 mod5=3 not divisible, length 4. ok.
Test: n=5, x=5, a=2,3,1,4,0. total=10 mod5=0. P1=2 (first=1,last=1), P2=5 mod5=0, P3=1 (update last=3), P4=1+4=5 mod5=0, P5=0. So first=1, last=3. answer = max(3,5-1=4)=4. suffix length =5-1=4 -> sum of indices 2-5: 3+1+4+0=8 mod5=3 not divisible. So answer 4. Could there be subarray of length 5? whole array sum 10 divisible, not allowed. So 4 is max.
Now, is there any scenario where using first_nonzero and last_nonzero as above gives the correct max? In the previous example, last_nonzero=3 gives prefix length 3 (indices 1..3 sum=2+3+1=6 mod5=1 not divisible) length 3; suffix length 4 is better. So ok.
Now consider an example where there are non-zero residues at both early and late positions but the earliest non-zero is not the one that yields longest suffix because maybe using a different i (not the smallest) but with a different j not equal to n might yield longer? But we argued that cannot exceed n - i_min because j <= n, and any i > i_min gives smaller length n - i. So suffix using i_min is longest possible suffix because length is decreasing as i increases. So that's optimal.
Thus solution is O(n) per test case.
But wait: What about the possibility that total_mod !=0 but there might be an even longer subarray that is not the whole array? That would be contradictory because whole array length n is maximum possible. So it's fine.
Thus implementation is straightforward.
But we must be cautious: In some problems, "subarray" can be empty? Usually not. The definition says deletion of several from beginning and end; deletion of all elements would result in empty subarray? Usually subarray is non-empty. In many Codeforces problems, subarray is non-empty. The examples confirm that: they output -1 if no such subarray exists, meaning there is no non-empty subarray with sum not divisible. So we consider non-empty subarrays.
Our method yields at least 1 if there is any non-zero residue. That would correspond to a subarray of length 1 if that a_i itself not divisible? Actually if there is a non-zero prefix sum at index i, it does not guarantee that a_i alone is not divisible. For instance, x=5, array: [5,1] => total=6 mod5=1 not zero, answer=2 (whole array). But suppose total=0, array: [5,5] -> all prefix mods =0 -> no non-zero, answer -1. But array: [5,1,4] total=10 mod5=0, prefix_mods: P1=0, P2=1 (first=2,last=2), P3=0. So first_nonzero=2, last_nonzero=2. answer = max(2, 3-2=1) =2. So longest is prefix length 2 (indices1-2 sum=5+1=6 mod5=1) which is valid; or suffix length 1 (index3 alone? Actually suffix starting at i+1=3 gives subarray [3], a3=4 mod5=4 not divisible, length1). So max=2. But does a single element subarray of length 1 with sum not divisible exist? In this array, element 5: divisible, element 1: not divisible? Wait a_2=1 not divisible by 5? Actually 1 mod5=1 not 0, so subarray [2] length 1 sum=1 not divisible. That's index2 alone. That corresponds to i=1 (P[1]=0) and j=2 (P[2]=1) -> length =1. So indeed we have length 1. But our algorithm gives suffix length = n - first_nonzero = 3-2=1 (which is that same subarray? Actually suffix from i+1=3? Wait first_nonzero=2, so i=2, suffix starting at 3 gives subarray [3] length1? That's index3 alone, sum=4 not divisible. That's also a length1 subarray but different. So we have multiple length1 subarrays. So answer 2 is correct. So the approach works.
Now, confirm that first_nonzero is defined as smallest i (1-indexed) with prefix_mod !=0. That yields suffix starting at i+1. But note that the subarray from i+1 to n includes elements after i. But what about the subarray from 1 to i? That's prefix length i, which may or may not have sum not divisible. But we also compute last_nonzero for prefix candidate.
Now, consider a subtle case: Suppose total_mod=0 and first_nonzero = k, but there is also a prefix with length > k that has sum not divisible? That would mean there exists j > k with P[j] != 0. That j would be captured by last_nonzero. So we are already considering the maximum j.
Now, what about the scenario where first_nonzero = k, but the suffix from k+1 to n sum is divisible? Wait we said if total_mod=0, then suffix sum = total - prefix_sum up to k = -P[k] mod x. Since P[k] != 0, suffix sum mod x = -P[k] != 0. So definitely not divisible. So it's valid. Good.
Similarly, prefix candidate: if P[j] != 0, then subarray 1..j sum = P[j] !=0, valid.
Thus algorithm yields valid subarray.
Now, why is this problem reminiscent of Codeforces problem "Ehab and another another problem"? Actually I recall a Codeforces problem: "Ehab and a component choosing problem"? Not sure. But this is known: longest subarray with sum not divisible by x: answer is n if total sum not divisible; else if there is at least one element not divisible, answer n-1; but wait typical known problem: "If the sum of the whole array is not divisible by x, answer n; else, we can try to remove one element from left or right that is not divisible by x; if such exists, answer n-1; else answer -1." That is a known solution? Let's check: In many problems, the answer is either n (if total sum not divisible) or if total sum divisible, we can try to find an element not divisible by x, then answer n-1. But is it always n-1? Let's test with earlier example: n=5, x=5, a=[1,4,5,0,0], total sum=10 divisible, we have element 1 (not divisible), element 4 (not divisible), but answer was 4 = n-1? n=5, n-1=4, correct. In example a=[2,3,5,0,0], answer 4 (n-1). In a=[1,4,0,0,0] total=5 divisible, answer? prefix last_nonzero=1? Actually compute: P1=1 (first=1,last=1), P2=5mod5=0, rest 0. So answer = max(1,5-1=4)=4 = n-1. So it seems when total divisible, answer is either n-1 or -1? But earlier we had a case where answer was 2 for n=3? That's n-1? n=3, n-1=2, yes. So it suggests answer might be n-1 if any element not divisible? But wait, consider a case where the whole array sum divisible, and there is at least one element not divisible, is it always possible to get a subarray of length n-1 with sum not divisible? Not necessarily? Let's think.
If total sum divisible, and we have at least one element a_i not divisible by x, can we always remove one element to get sum not divisible? The sum of the rest = total - a_i. Since total % x = 0, rest % x = -a_i % x != 0. So the subarray consisting of all elements except a_i has sum not divisible. That subarray length is n-1. However, is that subarray contiguous? Removing an element from the array yields either two disjoint parts if we remove a middle element, not a single contiguous subarray. But if we remove one element from either the beginning or the end, the remaining is a contiguous subarray of length n-1. But if we remove a middle element, we get two separate subarrays, not a single contiguous subarray. So the only contiguous subarrays of length n-1 are the prefix that excludes the last element, and the suffix that excludes the first element. So if we want length n-1, we need either the first element or the last element to be not divisible by x. Because then removing it yields a contiguous block. But what if the only element not divisible is in the middle? Then we cannot get a length n-1 contiguous subarray by removing that element; we would need to remove either first or last element, but if those are divisible, the sum of the rest might be divisible? Let's examine.
Suppose total sum divisible by x. If we remove first element (which is divisible by x), the sum of remaining = total - a_1, and since a_1 % x =0, remaining sum % x = 0, so that subarray sum divisible. Similarly, if we remove last element and it is divisible, sum remains divisible. So we need either first or last element not divisible to get length n-1. If neither first nor last is not divisible, then we cannot get length n-1; maybe the longest is smaller.
Our earlier algorithm handles this: first_nonzero is the smallest index i where prefix_mod !=0. That i might not be 1. For length n-1 to be achievable, we need either first_nonzero = 1 (so prefix length 1 is non-zero? Actually that would give suffix from 2 to n length n-1 not divisible) or last_nonzero = n (but last_nonzero cannot be n because total_mod=0 implies P[n]=0, so last_nonzero ≤ n-1). Actually for prefix length n-1, we need j = n-1 with P[n-1] !=0. That is last_nonzero = n-1. So if last_nonzero = n-1, then prefix of length n-1 works. Or if first_nonzero = 1, suffix length n-1 works. So the answer might be n-1 only in those cases; otherwise, answer could be less than n-1.
But wait, earlier we thought if any element not divisible, we could remove that element to get length n-1, but that removal might not be contiguous. So it's not valid. So the known solution for this problem is not simply "n-1 if any element not divisible". The correct solution is as derived: answer = n if total_mod !=0 else max( longest prefix with sum not divisible, longest suffix with sum not divisible). This yields answer n-1 only if either first element not divisible or last element not divisible (or more generally if either the prefix sum up to n-1 is not divisible or the suffix from 2 to n is not divisible). But it's possible that both first and last are divisible, but we still might get n-1? Let's check: if first and last are divisible, can we get a subarray of length n-1 that excludes a middle element? That would be non-contiguous, so not allowed. So n-1 not possible. So answer would be less than n-1. So the algorithm matches.
But let's verify with a concrete example: n=4, x=3, a=[3,1,2,3]. total sum = 9 mod3=0. first element a1=3 divisible, last a4=3 divisible. Now prefix sums: P1=0 (since 3%3=0), P2=1 (first_nonzero=2,last_nonzero=2), P3= (1+2)=3 mod3=0, P4=0. So first_nonzero=2, last_nonzero=2. answer = max(2, 4-2=2) =2. So answer is 2, not 3. Is there a subarray of length 3 not divisible? Check all length 3 subarrays: [3,1,2] sum=6 divisible by 3? 6%3=0. [1,2,3] sum=6%3=0. So none. length 2 subarrays: [3,1] sum=4%3=1 not divisible; [1,2] sum=3%3=0; [2,3] sum=5%3=2 not divisible. So longest length is 2. So algorithm correct.
Thus the simple solution is correct.
Now, before finalizing, we must consider the possibility that total_mod !=0 but there could be a longer subarray than n? No.
Hence solution per test case:
- Compute total_mod and track first and last indices where prefix_mod !=0.
- If total_mod != 0: print n
- Else if no such indices: print -1
- Else: print max(last_nonzero, n - first_nonzero)
Time O(n) per test case, memory O(1).
Now we need to produce final answer.
But wait: There's another nuance: The prefix_mod is computed as sum mod x. But sum of subarray is not necessarily prefix_mod difference mod x? Actually we want (P[j] - P[i]) mod x !=0, which is equivalent to P[j] != P[i] mod x. So our analysis holds.
Now check with sample input: Provided earlier, matches.
Thus we can produce code.
But we also have to handle multiple test cases, and large n. Input up to 1e5 per test, total up to maybe 5e5, fine.
Edge Cases:
-
n=1: If a[1] % x !=0: total_mod !=0, answer =1. Else total_mod=0, and check if any non-zero prefix_mod? P[1]=0, no non-zero, answer -1. So correct.
-
x=1: Any integer mod 1 =0, so all sums divisible by 1. total_mod always 0, and all prefix_mods are 0. So first_nonzero never set, answer -1. Correct.
-
x=0? Not allowed, x >=1.
-
a_i can be 0, as in example.
Thus solution works.
Now, I will write final answer in Python, with fast I/O due to up to 5e5 numbers.
Implementation:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return it = iter(data) t = int(next(it)) out = [] for _ in range(t): n = int(next(it)); x = int(next(it)) pref = 0 first = -1 last = -1 for i in range(1, n+1): a = int(next(it)) pref = (pref + a) % x if pref != 0: if first == -1: first = i last = i total_mod = pref if total_mod != 0: out.append(str(n)) elif first == -1: out.append("-1") else: ans = max(last, n - first) out.append(str(ans)) sys.stdout.write("\n".join(out))
Test with provided example: Input: 3 3 3 1 2 3 3 4 1 2 3 2 2 0 6
Our code: Case1: n=3, x=3: a=[1,2,3], pref steps: 1->1 (first=1,last=1); 3->0; 6->0. total_mod=0, first=1,last=1 => ans=max(1,2)=2. Case2: total_mod=2 !=0 => ans=3. Case3: n=2, x=2: a=[0,6]; pref: 0->0; 6->0; total_mod=0, first stays -1 => -1. Matches.
Now, I want to double-check with some random tests by brute force for small n to ensure no oversight. I can reason: The derived condition is exactly the maximum distance between two prefix sums with different mod values, which we argued reduces to max(last_nonzero, n - first_nonzero) when total_mod=0. But is it always correct that the maximum distance between two different residues is either from 0 to a non-zero or from a non-zero to n? Because there might be two non-zero residues that are far apart, but we argued that distance between them is less than or equal to both candidates. Let's prove formally.
We have indices from 0 to n. Let S be set of indices with residue r. Let R be set of residues. For any two residues p != q, let i_p = min index with residue p, j_p = max index with residue p. Similarly for q. The maximum distance between an index of residue p and an index of residue q is max(j_q - i_p, j_p - i_q). Since p and q are arbitrary.
We want global maximum over all pairs p != q.
Now, if total_mod = 0, we know that residue 0 appears at indices 0 and n (both). So for residue 0, i0 = 0, j0 = n. For any non-zero residue r, we have i_r ≥ 1 (since index0 is residue0) and j_r ≤ n-1 (since n is residue0). So consider any pair (p, q). If one of them is 0, say p=0, q=r !=0, then possible distances: j_r - i0 = j_r, and j0 - i_r = n - i_r. So max over r !=0 of max(j_r, n - i_r) = max( max_j_nonzero, n - min_i_nonzero). This is candidate1.
If both p and q are non-zero, then distance candidates: j_q - i_p and j_p - i_q. Without loss assume i_p ≤ i_q. Then j_q - i_p ≤ j_q ≤ max_j_nonzero. And j_p - i_q ≤ j_p - i_p? Actually j_p - i_q ≤ j_p - i_p (since i_q ≥ i_p) ≤ j_p ≤ max_j_nonzero. Also j_q - i_p ≤ j_q - min_i_nonzero ≤ max_j_nonzero - min_i_nonzero, which is less than max_j_nonzero if min_i_nonzero>0. And also j_p - i_q ≤ max_j_nonzero - min_i_nonzero. Meanwhile n - min_i_nonzero could be larger. So indeed the maximum over non-zero pairs is at most max(max_j_nonzero - min_i_nonzero, ...). But max_j_nonzero - min_i_nonzero is less than both max_j_nonzero and n - min_i_nonzero (since min_i_nonzero>0 and max_j_nonzero<n). So it is less than the candidate from pairing with 0. Thus global maximum is from pairing residue 0 with some non-zero residue. So indeed answer = max(max_j_nonzero, n - min_i_nonzero). So our reasoning holds.
Thus solution is correct.
Now I'll output final answer.
But note: In problem statement, "subarray" is defined as contiguous segment (by deletion from beginning and end). So yes.
Thus code is ready.
Now, final step: Produce final answer in requested format: For each test case, print answer.
One more nuance: There might be scenario where first_nonzero = last_nonzero = same index, which is fine.
Thus done.
Now, write final message with explanation and code. ```python
import sys
def solve() -> None: data = sys.stdin.buffer.read().split() if not data: return it = iter(data) t = int(next(it)) out_lines = [] for _ in range(t): n = int(next(it)) x = int(next(it)) pref = 0 # prefix sum modulo x first = -1 # smallest index with non‑zero modulo last = -1 # largest index with non‑zero modulo for i in range(1, n + 1): a = int(next(it)) pref = (pref + a) % x if pref != 0: if first == -1: first = i last = i total_mod = pref if total_mod != 0: out_lines.append(str(n)) elif first == -1: out_lines.append("-1") else: ans = max(last, n - first) out_lines.append(str(ans)) sys.stdout.write("\n".join(out_lines))
if name == "main": solve()
-