To make the arithmetic mean be equal to exactly $$$1$$$ the sum needs to be equal to the number of elements in the array.

Let's consider $$$3$$$ cases for this problem:

1) The sum of the array equals $$$n$$$: Here the answer is $$$0$$$ since the arithmetic mean of the array is initially $$$1$$$.

2) The sum of the array is smaller than $$$n$$$: The answer is always $$$1$$$ since we can add a single integer $$$k$$$ such that $$$sum + k = n + 1$$$ is satisfied and more specifically $$$k = n - sum + 1$$$.

3) The sum of the array is greater than $$$n$$$: If we add any number apart from $$$0$$$ will add to the sum more or equal than to the number of elements. The number of $$$0$$$'s to add can be found by a loop of adding $$$0$$$'s until the number of elements is equal to the sum or by the simple formula of $$$sum-n$$$.

#include "bits/stdc++.h"
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int sum = 0;
        for (int i = 0;i < n; i++){
            int a;
            cin >> a;
            sum += a;
        }

        cout << sum - n << "\n";
    }
}

#include "bits/stdc++.h"
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n, m, i, j;
        cin >> n >> m >> i >> j;

        cout << 1 << " " << 1 << " " << n << " " << m << "\n";
    }
}

#include "bits/stdc++.h"
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> h(n);

        for (int i = 0;i < n; i++){
            cin >> h[i];
        }
        sort(h.begin(), h.end());

        if(n == 2){
            cout << h[0] << " " << h[1] << "\n";
            continue;
        }

        int pos = -1, mn = INT_MAX;

        for (int i = 1;i < n; i++){
            if(mn > abs(h[i] - h[i - 1])){
                pos = i;
                mn = abs(h[i] - h[i - 1]);
            }
        }
        
        for (int i = pos;i < n; i++){
            cout << h[i] << " ";
        }
        for(int i = 0;i < pos; i++){
            cout << h[i] << " ";
        }

        cout << "\n";

    }
}

#include "bits/stdc++.h"
using namespace std;

string get(string s, int k){
    while((int)s.size() < k){
        s = s + s;
    }
    while((int)s.size() > k)
        s.pop_back();
    return s;
}
int main()
{
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    string pref = "";
    pref += s[0];

    string mn = get(pref, k);

    for(int i = 1;i < n;i++){
        if(s[i] > s[0])break;
        pref += s[i];
        mn = min(mn, get(pref, k));
    }
    cout << mn << "\n";
}

#include "bits/stdc++.h"
using namespace std;

string get(string s, int k){
    while((int)s.size() < k){
        s = s + s;
    }
    while((int)s.size() > k)
        s.pop_back();
    return s;
}
int main()
{
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    string pref = "";
    pref += s[0];

    string mn = get(pref, k);

    for(int i = 1;i < n;i++){
        if(s[i] > s[0])break;
        pref += s[i];
        mn = min(mn, get(pref, k));
    }
    cout << mn << "\n";
}

We know that the final string is some prefix repeated a bunch of times. Incrementally for $$$i$$$ from $$$1$$$ to $$$n$$$ we will keep the longest among the first $$$i$$$ prefixes that gives the best answer we've seen so far.

So assume the $$$m-th$$$ prefix is currently the best and we're considering position $$$p$$$. If the $$$p-th$$$ character is greater than the corresponding character in $$$s_{1..m} \cdot (a lot)$$$ then the $$$p-th$$$ prefix and any further prefixes can't possibly give a smaller answer, so we just print the current one and finish. Otherwise all the characters before the $$$p-th$$$ are all less than or equal to the corresponding characters in $$$s_1..m \cdot (a lot)$$$, so if the $$$p-th$$$ is smaller than the corresponding we set the $$$p-th$$$ prefix as the best.

Now the interesting case is if the current character is the same as the corresponding one. Say then that $$$p = m + k$$$, by the logic of the previous paragraph we must have $$$s_{(m + 1)..(m + k)} = s_{1..k}$$$. If $$$k = m$$$ then the new prefix is just the old one twice, so set $$$p$$$ as the best prefix now. This ensures that otherwise $$$k < m$$$.

Denote $$$A = s_{1..k}$$$ and $$$B = s_{(k + 1)..m}$$$, so the string formed by the current best prefix is $$$ABABABABA...$$$ and the new one is $$$ABAABAABA...$$$ Now if $$$AB = BA$$$ then these strings are in fact the same, so set $$$m + k$$$ as the new best prefix. Otherwise we can find the first position where $$$AB$$$ and $$$BA$$$ differ, and use that to determine whether the new prefix is better. This can be done in $$$O(1)$$$ with Z function, thus giving a linear solution for the full problem.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
int n, k;

vector<int> z_func(string &s) {
    int n = s.size(), L = -1, R = -1;
    vector<int> z(n);
    z[0] = n;
    for(int i = 1; i < n; i++) {
        if(i <= R)
            z[i] = min(z[i - L], R - i + 1);
        while(i + z[i] < n && s[i + z[i]] == s[z[i]])
            z[i]++;
        if(i + z[i] - 1 > R) {
            L = i;
            R = i + z[i] - 1;
        }
    }
    return z;
}

void finish(int m) {
    for(int i = 0; i < k; i++)
        cout << s[i % m];
    cout << '\n';
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k >> s;
    auto z = z_func(s);

    int cur = 1;
    for(int i = 1; i < n; i++) {
        if(s[i] > s[i % cur])
            finish(cur);
        if(s[i] < s[i % cur]) {
            cur = i + 1;
            continue;
        }
        int off = i - cur + 1;
        if(off == cur) {
            cur = i + 1;
            continue;
        }
        if(z[off] < cur - off) {
            if(cur + off + z[off] >= k) {
                cur = i + 1;
                continue;
            }
            if(s[off + z[off]] > s[z[off]])
                cur = i + 1;
            continue;
        }
        if(z[cur - off] < off) {
            if(2 * cur + z[cur - off] >= k) {
                cur = i + 1;
                continue;
            }
            if(s[cur - off + z[cur - off]] < s[z[cur - off]])
                cur = i + 1;
            continue;
        }
        cur = i + 1;
    }

    finish(cur);
}

#include "bits/stdc++.h"
using namespace std;

const int N = 2e5 + 10;
vector<int> adj[N];
int s[N], n, m;
bool bipartite()
{
    bool bip = true;

    for(int i = 0;i < n;i++)
        s[i] = -1;

    queue<int> q;

    for(int i = 0;i < n;i++){
        if(s[i] != -1)continue;

        q.push(i);
        s[i] = 0;

        while(!q.empty()){
            int v = q.front();
            q.pop();

            for(int u: adj[v]){
                if(s[u] == -1){
                    s[u] = s[v] ^ 1;
                    q.push(u);
                }else bip &= s[u] != s[v];
            }
        }
    }
    return bip;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        for(int i = 0;i < n;i++)
            adj[i].clear();
        vector<int> v(n), t(n);

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

        for(int i = 0;i < m;i++){
            int a, b;
            cin >> a >> b;
            --a, --b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        if(bipartite() == false){
            cout << "YES\n";
        }else{
            vector<int> c(2, 0);

            for(int i = 0;i < n;i++){
                c[s[i]] += v[i] - t[i];
            }

            if(c[0] == c[1]){
                cout << "YES\n";
            }else cout << "NO\n";
        }
    }

}