PROBLEM LINK:
Setter: Manuj Nanthan
Tester: Aryan Choudhary
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
SIMPLE
PREREQUISITES:
PROBLEM:
Given a number N, we need to find the number of distinct valuyes possible for i \oplus j where 1 \leq i, j \leq N.
EXPLANATION:

If N = 1, the possible xor values are 1 \oplus 1 = 0 which has 1 unique value.

If N = 2, the possible xor values are 1 \oplus 1 = 0, 1 \oplus 2 = 1, 2 \oplus 2 = 0 which has 2 unique values.

For the remaining cases, we consider N \geq 3.

Let us define x as the highest power for which 2^x \leq N.

Suppose 2^x \lt N. I claim that we can get all the numbers from 0 to 2^{x+1} 1. This can be achieved by the following way:

For the numbers num which have bit x set and are greater than 2^x, it can be formed by (2^x, 2^x \oplus num). For example, let N = 12, then we have x = 3. Number 12 (1100 in binary ) can be formed by (2^3(1000), 4(0100)).

Number 0 can be formed by (1, 1) since 1 \oplus 1 = 0. Number 1 can be formed by (2, 3) since 2 \oplus 3 = 1. For the remaining numbers 1 \lt num \leq 2^x, we can simply get them as (1, num \oplus 1). For example, 2 = 1 \oplus 3, 3=1 \oplus 2 and so on.

By the property of xor, num \oplus 1 is either num +1 or num 1, so if 1 \lt num \leq 2^x \lt N, 1 \leq num \oplus 1 \leq N. Hence these pairs of numbers will always be valid.

Now what happens if 2^x = N ? All of the above cases hold true except for the case of num = 2^x. We cannot get this from any xor pair (i, j) where 1 \leq i, j \leq 2^x. Since the only number with bit x set is 2^x, we must keep i = 2^x. Then for i \oplus j = 2^x, we must keep j=0, which we cannot do since j \geq 1. Hence, in this case, except 2^x, we can get xor pair for any number from 0 to 2^{x + 1} 1.
TIME COMPLEXITY:
O(\log N) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
int tests;
cin >> tests;
while (tests) {
ll n;
cin >> n;
ll ans = 1;
int MOD = 1e9 + 7;
// Special case
if (n == 2) {
cout << 2 << endl;
continue;
}
while (ans < n) {
ans *= 2;
}
if (ans == n) {
ans *= 2;
ans;
}
cout << ans % MOD << endl;
}
return 0;
}
Setter's solution
#from itertools import *
#from math import *
#from bisect import *
#from collections import *
#from random import *
#from decimal import *
#from heapq import *
#from itertools import * # Things Change ....remember :)
import sys
input=sys.stdin.readline
def inp():
return int(input())
def st():
return input().rstrip('\n')
def lis():
return list(map(int,input().split()))
def ma():
return map(int,input().split())
t=inp()
p=10**9 + 7
while(t):
t=1
n=inp()
if(n<=2):
print(n)
else:
x=bin(n)[2:]
res=pow(2,len(x),p)
if(x.count('1')==1):
res=1
print(res%p)
Tester's solution
def main():
mod=10**9+7
for _ in range(int(input())):
n=int(input())
if n<=2:
print(n)
elif n&(n1):
print(pow(2,len(bin(n))2,mod))
else:
print((2*n1)%mod)
main()
Please comment below if you have any questions, alternate solutions, or suggestions.