Approach 1: Brute Force Method

A straightforward solution involves checking all possible combinations of three indices using nested loops. This approach iterates through every possible triplet (i, j, k) in the array.

The time compleixty is O(T × N³), which is impractical given the constraint 3 ≤ n ≤ 2 × 10⁵. This method would exceed time limits and is not recommended for actual implementation.

Approach 2: Digit-Based Optimization

Key insight: The unit digit of the sum a[i] + a[j] + a[k] depends solely on the unit digits of the three numbers.

If the sum of the unit digits modulo 10 equals 3, then the sum of the original numbers will also have a unit digit of 3.

We can maintain a frequency array digitCount\[10\] to track occurrences of each unit digit (0-9) in the input array. For each potential combination of three digits, we temporarily decrement their counts, verify availability (non-negative), check if their sum modulo 10 equals 3, and then restore the counts.

Important considerations:

• The sum of unit digits might exceed 9, so we must apply modulo 10 operation
• Simple presence tracking is insufficient - we must maintain exact counts to avoid false positives

Implementation example:

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

int testCaseCount;
int arraySize;
int digitFrequency[10];

int fastInput() {
    int result = 0, sign = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        result = result * 10 + (ch - '0');
        ch = getchar();
    }
    return result * sign;
}

int main() {
    scanf("%d", &testCaseCount);
    
    for (int currentCase = 0; currentCase < testCaseCount; currentCase++) {
        arraySize = fastInput();
        memset(digitFrequency, 0, sizeof(digitFrequency));
        
        for (int index = 0; index < arraySize; index++) {
            int value = fastInput();
            digitFrequency[value % 10]++;
        }
        
        bool foundSolution = false;
        
        for (int first = 0; first <= 9 && !foundSolution; first++) {
            for (int second = 0; second <= 9 && !foundSolution; second++) {
                for (int third = 0; third <= 9 && !foundSolution; third++) {
                    digitFrequency[first]--;
                    digitFrequency[second]--;
                    digitFrequency[third]--;
                    
                    bool validCombination = (digitFrequency[first] >= 0) &&
                                          (digitFrequency[second] >= 0) &&
                                          (digitFrequency[third] >= 0);
                    
                    if (validCombination && ((first + second + third) % 10 == 3)) {
                        foundSolution = true;
                    }
                    
                    digitFrequency[first]++;
                    digitFrequency[second]++;
                    digitFrequency[third]++;
                }
            }
        }
        
        printf(foundSolution ? "YES\n" : "NO\n");
    }
    return 0;
}

Approach 3: Precomputed Valid Combinations

We can observe that only specific digit triplets satisfy the condition. By precomputing all valid combinations once, we can efficiently check against input data during each test case.

This approach enumerates all possible digit combinations (0-9) where their sum modulo 10 equals 3, storing them in a lookup table for quick verification.

Core implementation:

int validTriplets[90][3] = {
    {0,0,3},{0,1,2},{0,2,1},{0,4,9},{0,5,8},{0,6,7},{0,7,6},{0,8,5},{0,9,4},
    {1,0,2},{1,1,1},{1,3,9},{1,4,8},{1,5,7},{1,6,6},{1,7,5},{1,8,4},{1,9,3},
    // ... complete list of valid combinations
};

bool checkValidCombinations(int digitFrequency[10]) {
    for (int i = 0; i < 90; i++) {
        if (digitFrequency[validTriplets[i][0]] > 0 &&
            digitFrequency[validTriplets[i][1]] > 0 &&
            digitFrequency[validTriplets[i][2]] > 0) {
            
            if (validTriplets[i][0] == validTriplets[i][1] && 
                validTriplets[i][1] == validTriplets[i][2]) {
                if (digitFrequency[validTriplets[i][0]] >= 3) return true;
            } else if (validTriplets[i][0] == validTriplets[i][1] || 
                      validTriplets[i][1] == validTriplets[i][2] || 
                      validTriplets[i][0] == validTriplets[i][2]) {
                if ((validTriplets[i][0] == validTriplets[i][1] && 
                     digitFrequency[validTriplets[i][0]] >= 2) ||
                    (validTriplets[i][1] == validTriplets[i][2] && 
                     digitFrequency[validTriplets[i][1]] >= 2) ||
                    (validTriplets[i][0] == validTriplets[i][2] && 
                     digitFrequency[validTriplets[i][0]] >= 2)) {
                    return true;
                }
            } else {
                return true;
            }
        }
    }
    return false;
}

Code to generate the lookup table:

for (int a = 0; a <= 9; a++) {
    for (int b = 0; b <= 9; b++) {
        for (int c = 0; c <= 9; c++) {
            if ((a + b + c) % 10 == 3) {
                printf("{%d,%d,%d},", a, b, c);
            }
        }
    }
}