SUBSUM3 - Editorial

[iceknight1093]

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given an array A. Does it contain a non-empty subsequence whose sum is a multiple of 3?

EXPLANATION:

There are a couple of different ways to approach this.
One is to look at a bit of casework.

First, if A contains any element that’s a multiple of 3, we can just take that single element and be done.
So, we only need to deal with arrays that don’t contain a multiple of 3 at all.

Since there are no multiples of 3, every element has a remainder of either 1 or 2 when divided by 3.
If we have some element which has a remainder of 1, and another element that has a remainder of 2, we can take these two elements to obtain a sum divisible by 3.

Why?

Suppose a = 3x+1 and b = 3y+2, so that a has a remainder of 1 when divided by 3, and b has a remainder of 2.

Then, a+b = 3x+1 + 3y+2 = 3\cdot (x+y+1) is a multiple of 3.

That leaves us with the case where every element has the same remainder when divided by 3: either everything has remainder 1, or everything has remainder 2.
In either case, if we have at least three elements, taking three of them will give a sum that’s divisible by 3. If there are only one or two elements, it’s impossible.

---

Simply implementing the three checks above will pass:

• Check for a multiple of 3.
• If not, check for both remainder 1 and remainder 2 existing.
• If not, the answer is “Yes” if N \geq 3 and “No” otherwise.

Alternately, observe that as long as N \geq 3, one of the above three conditions will definitely be true (even just looking at the first three elements of the array).
So, when N \geq 3 you can immediately answer “Yes”, after which N = 1 and N = 2 can be handled with manual casework: there’s only one possibility to check for when N = 1, and three for N = 2 (A_1, A_2, A_1+A_2).

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ct = [0]*3
    for x in a: ct[x%3] += 1
    
    ans = 'No'
    if ct[0] > 0: ans = 'Yes'
    if min(ct[1], ct[2]) > 0: ans = 'Yes'
    if max(ct[1], ct[2]) > 2: ans = 'Yes'
    print(ans)

Author's code (C++)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> a(n);
    for (auto &x : a){
        cin >> x;
    }
    
    if (n == 1){
        if (a[0] % 3 == 0){
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
        return;
    }
    
    if (n == 2){
        if (a[0] % 3 == 0 || a[1] % 3 != a[0] % 3){
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
        return;
    }
    
    cout << "Yes\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}