Can anyone please help me(facing TLE) ? question - MULTHREE

help
1

using namespace std;

int main() {
// your code goes here
int tests = 0;
cin >> tests;

while(tests--){
    long long int K = 0;
    int d0 = 0, d1 = 0, sum = 0;
    cin >> K >> d0 >> d1;
    sum = d0 + d1;
    for(int i = 2; i < K; i++){
        sum += (sum%10);
    }
    cout << ((sum%3==0)?"YES":"NO") << endl;
}

return 0;

}

2

Check if 2^(K-2) * (d0+d1)is divisible by 3.

E.g 5 3 4

2^3 * (3+4)
= 8*7 = 56

Since 56 is not divisible by 3, so the above 5 digit no. is not divisible by 3

1 Like
3

donot go with brute force since input is very large. you can directly observe that pattern is repeating so so find sum of repeating term ex:
13 8 1 then: all terms are 819 8624 8624 86 you can see 8 6 2 4 is repeating so u can easily find the sum and if sum of digit is divisible by 3 the no is divisible by 3

1 Like