Odd Even

Easy
0/40
Average time to solve is 10m
profile
Contributed by
11 upvotes
Asked in company
TCS

Problem statement

Alice has two numbers, 'X' and 'Y'. He is asked to perform the following operations any number of times.

Alice adds 1 to 'X' if 'X' is odd. Alice adds 2 to 'X' if 'X' is even. Will he be able to make 'X' equal to 'Y'?


Return 1 if 'X' can be made equal to 'Y' using the above operations any number of times(possibly 0) and 0 otherwise.

Note: Assume 1-based indexing.


For example: 
Let 'X' = 3 and 'Y' = 6, Alice adds 1 to 'X' since 'X' is odd. Now 'X' will become 4. Then, Alice will add 2 to 'X', since 'X' is even, and it will become 6. 'X' becomes equal to 'Y'. Hence we will return 1 as the answer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:- 
The first line contains an integer 'T', which denotes the number of test cases.
For every test case:-
The first line contains two integers, 'X' and 'Y', the variables mentioned above.
Output Format:- 
For each test case, Return 1 if 'X' can be made equal to 'Y' using the above operations any number of times(possibly 0) and 0 otherwise.
Note:- 
You don’t need to print anything. Just implement the given function.
Constraints:- 
1 <= 'T' <= 10
1 <= 'X', 'Y' <= 10^9
Time Limit: 1 sec
Sample Input 1:-
2
4 8
1 1
Sample Output 1:-
1
1
Explanation of sample input 1:-
First test case:- 
In 1st operation, Alice will add 2 to 'X' as 'X' is even. Now, 'X' is 6. Again, in the 2nd operation, Alice will add 2 to 'X'. Now 'X' is 8, which is equal to 'Y'. So, the answer is 1.

Second test case:-
'X' is already equal to 'Y'. So, the answer is 1.
Sample Input 2:-
2
4 9 
7 8
Sample Output 2:-
0
1
Hint

Look for the parity of 'y'.

Approaches (1)
Mathematical Approach

Approach:-

 

If 'x' > 'y', 'x' can never be made equal to 'y'.

If 'y' is even, we can always make 'x' equal to 'y' by performing some number of operations. 

If 'y' is odd, Let's take two cases:

  • If 'x' is even, we will always get an even number, As we always add 2 to 'x'.
  • If 'x' is odd, then after 1 operation, 'x' will be even, as we are adding 1 to 'x'. After this, 'x' will always be even after any number of operations.

So, when 'y' is odd, it is impossible to make 'x' equal to 'y' except if 'x' is already equal to 'y'.

           

 Algorithm:-

 

  • Check if 'x' and 'y' are already equal.
    • Return 1.
  • Check if 'x' is greater than 'y'.
    • Return 0.
  • Check if 'y' is odd.
    • Return 0.
  • Else
    • Return 1.
Time Complexity

O(1),

since we are only using the if-else condition, it takes O(1) time. Hence, The overall time complexity is of the order O(1). 

Space Complexity

O(1).

since we are not using any variable, which will take O(1) space. so, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Odd Even
Full screen
Console