PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: manasagarwal12
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
1490
PREREQUISITES:
None
PROBLEM:
Given an odd integer N, find two integers x and y such that
(x\mid y)\cdot (x\oplus y) = N
EXPLANATION:
There are a couple of different solutions, but perhaps the simplest is to notice that you can always choose x = N and y = N-1.
This works because N is odd, meaning it has its last bit set.
N-1 thus has exactly the same binary representation, but the last bit is unset instead.
For example, if N = 27, in binary we have
27 = 11011_2 \\
26 = 11010_2 \\
where only the last bit differs.
So,
- x\mid y = N\mid (N-1) = N, since every bit set in (N-1) is also set in N.
- x\oplus y = N\oplus (N-1) = 1, since the only bit where N and (N-1) differ is the last one.
So, the product is just N\cdot 1 = N.
TIME COMPLEXITY
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print(n-1, n)