# SubArray
## Problem
Given an array of $n$ distinct integers, print the size of a maximal subarray of $S$ where the sum of any $2$ numbers in $S'$ is not evenly divisible by $k$.

### Input format
- The first line contains 2 space-separated integers $n$ and $k$, the number of values in $S$ and the non factor.
- The second line contains $n$ space-separated integers $a_1, a_2, ..., a_n$, which are the values of array $S$. Each $a_i$ is the unique value of the array.

### Output format
- Only one intergers, which is the length of subarray.

### Constraints
- $1 \leq n \leq 10^5$
- $1 \leq k \leq 100$
- $1 \leq a_i \leq 10^9$
- All of the given numbers in array are distinct.

### Example

Input:
4 3
1 7 2 4  

Output:
3 

**Explanation:**
The sums of all permutations of two elements from $S$:

1 + 7 = 8  
1 + 2 = 3  (divisible by k)
1 + 4 = 5  
7 + 2 = 9  (divisible by k)
7 + 4 = 11  
2 + 4 = 6  (divisible by k)

Only $S' = [1, 7, 4]$ is accepted

## Tutorial
### Greedy solution
#### Giải thích thuật toán
Với mỗi số trong dãy số $a$, ta thực hiện push dần các số vào một set kết quả(gọi là $ans$). Với các mỗi số (gọi là $v$) phải kiểm tra xem là các số trong $ans$ có thích hợp hay không, nói cách khác là có tồn tại giá trị $u$ trong $ans$ sao cho $(u+v)$ có chia hết cho $k$ hay không. Nếu có tồn tại thì có nghĩa $v$ không phù hợp.

    ans = []
    for v in (các số trong dãy a):
        if (tồn tại u in ans) and (u+v) mod k = 0:
            giá trị v không thích hợp
        else:
            v -> ans

    kết quả là len(ans)

**Nhận xét**: Đây là một cách giải theo hướng greedy nên sẽ không đảm bảo kết quả sẽ đúng.
#### Độ phức tạp
$O(n*n)$ (worst case)
#### Code

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;

int a[MAXN];

bool check(vector <int> arr, int val, int k){
    for(int u: arr)
        if((u+val) % k == 0)
            return false;
    return true;
}

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    vector <int> arr;
    for(int i = 0; i < n; i++){
        if(check(arr, a[i], k))
            arr.push_back(a[i]);        
    }
    cout << arr.size() << '\n';
}

### Accepted solution
#### Giải thích thuật toán
Nhận thấy: $(x + y) \bmod k = ((x \bmod k) + (y \bmod k)) \bmod k$.

Từ đó ta có thể biến đổi dãy số $a$ như sau $a_i = a_i \bmod k$, như vậy các số chỉ dao động từ $[0, k-1]$.

Do các số chỉ nằm trong $[0, k-1]$ nên những cặp tổng chia hết cho $k$ sẽ có dạng $(x, k - x)$ với $x$ là một số từ $0$ đến $k/2$ (do cặp có tính chất hoán vị nên chỉ xét từ $0$ đến $k/2$). Và với mỗi cặp, ta sẽ chọn vào kết quả là 1 trong 2 số $x$, $k-x$.

Từ đó nếu gọi $cnt(x)$ là số lần xuất hiện của phần tử $x$ thì trong 2 số $x$ và $k-x$ mình sẽ chọn số có $cnt$ lớn hơn để tối ưu kết quả.

Như vậy kết quả sẽ là $\sum_{x = 0}^{k/2} max(cnt(x), cnt(k-x))$

Lưu ý, công thức trên có trường hợp đặc biệt là cặp $(0, 0)$ và cặp $(k/2, k/2)$ (nếu k là số chẵn). Đối với 2 trường hợp này thì nếu $cnt$ > 0 thì chỉ chọn 1 số.

    for i in [1, n]:
        a[i] = a[i] mod k
        cnt[a[i]] += 1  
    
    ans = 0
    for i in [0, k/2]:
        if i = 0 or (k chẵn and i = k/2):
            ans += (cnt[i] > 0)
        else:
            ans += max(cnt[i], cnt[k - i])

    kết quả là ans

#### Độ phức tạp
$O(n)$
#### Code

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;

int a[MAXN], cnt[105];

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] = a[i] % k;
        cnt[a[i]]++;
    }
    int res = 0;
    for(int i = 0; i <= k/2; i++)
        if(i == 0 || i == (k+1)/2){
            res += (cnt[i] > 0);
        }else{
            res += max(cnt[i], cnt[k-i]);
        }
    cout << res << '\n';
}

i =