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;
		 }
   if(sum < n)cout << "1\n";
   else 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;
 
int main()
{
    int t;
    cin >> t;
 
    while(t--){
        
        int n;
        cin >> n;
        if(n % 2 == 1){
            cout << "Bob\n";
            continue;
        }
        int cnt = 0;
        while(n % 2 == 0){
            cnt++;
            n /= 2;
        }
 
        if(n > 1){
            cout << "Alice\n";
        }else if(cnt % 2 == 0){
            cout << "Alice\n";
        }else cout << "Bob\n";
    }
}
    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<long long> adj[N];
 long long s[N], n, m;
 bool bipartite()
 {
	 bool bip = true;

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

	 queue<long long> q;

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

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

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

			 for(long long 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);
	 long long T;
	 cin >> T;
	 while(T--)
	 {
		 cin >> n >> m;
		 for(long long i = 0;i < n;i++)
			 adj[i].clear();

		 vector<long long> v(n), t(n);
		long long p1 = 0, p2 = 0;
		 for(long long i = 0;i < n; i++){
			 cin >> v[i];
			 p1 = (p1 + abs(v[i])) % 2;
		 }
		 for (long long i = 0;i < n; i++){
			 cin >> t[i];
			 p2 = (p2 + abs(t[i])) % 2;
		 }

		 for(long long i = 0;i < m;i++){
			 long long a, b;
			 cin >> a >> b;
			 --a, --b;
			 adj[a].push_back(b);
			 adj[b].push_back(a);
		 }
		 
		 if(p1 != p2){
		   cout << "NO\n";
		   continue;
		 }

		 if(bipartite() == false){
			 cout << "YES\n";
		 }else{
			 vector<long long> 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";
		 }
	 }

 }