1

first input will be number of test cases t, then given two numbers a and b you have to perform i operations such that,

  • add 1 to a if i is odd
  • add 2 to a if i is even

now print YES if a can become equal to b and NO if it can't

when I tried to submit my solution i got error that time limit is exceeded.

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

int main()
{
    int t, a, b;
    cin >> t;
    while (t)
    {
        cin >> a >> b;
        int flag = 1;
        while (a != b && a < b)
        {
            if (flag % 2 == 0)
            {
                a += 2;
            }
            else
            {
                a += 1;
            }
            flag++;
        }
        if (a == b)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        t--;
    }
    return 0;
}
Aamir
  • 1,974
  • 1
  • 14
  • 18
Yuvraj
  • 11
  • 1
  • 1
    You shouldn't ever [`#include`](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)! – Aconcagua Jun 11 '22 at 04:39
  • 1
    If `a < b` then they *cannot* be equal either, so the first check for inequality is redundant and should be omitted. You could skip the `if` and the modulo operation if you start with `flag = 0` and do within the loop `a += 1 + flag; flag = 1 - flag;` which will always turn `flag` into `0` and `1` one after another. Still you don't need all this as there's a direct formula available, see given answer. – Aconcagua Jun 11 '22 at 04:42
  • 1
    About [`using namespace std`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)... – Aconcagua Jun 11 '22 at 04:48

2 Answers2

1

You don't need to actually iterate from a to b, just use the following observations to solve:

  • After 2 operations, the value of a increases by 3. So after an even number of operations (let number be 2k), a increases by 3k.
  • Similarly, for an odd number of operations (of form 2k+1), a increases by 3k+1.

As you can see, a can either be increased by 3k or 3k+1, which implies that b will be reachable from a if (b-a) mod 3 = (0 or 1) (and obviously, if b>a). You can check this in O(1) complexity.

Abhinav Mathur
  • 7,791
  • 3
  • 10
  • 24
0

The inner loop can be simplified into a math expression. We can come up with the model using some examples.

For example, if a = 10, b = 20.

Loop 1 a += 1 (11)
Loop 2 a += 2 (13)
Loop 3 a += 1 (14)
Loop 4 a += 2 (16)
...

We can see that after two operations, a increases by 3. Which can be generalized, that after the 2n operation (which represents an even number), that a increases by 3n. On the other hand after the 2n + 1 operation (odd numbers), a is equal to an increase of 3n + 1. Thus, a can be increased either by 3n or 3n+1. Thus, 3n or 3n+1 has to be able to be equal to the difference of a and b, which in this case is 10.

Thus either

1. 3 has to divide b - a, (b-a)%3 = 0 
2. 3 has to divide b - a with a remainder of 1, (b-a)%3=1

Thus, instead of a loop, using a mathematical expression can simply the runtime to O(1) per input.

akastack
  • 75
  • 7