XOR Equality(XOREQUAL) Solution — Codechef MayLong Challenge

Problem Statement

For a given N, find the number of ways to choose an integer x from the range [0,2N−1] such that x⊕(x+1)=(x+2)⊕(x+3), where ⊕ denotes the bitwise XOR operator.

Since the number of valid x can be large, output it modulo 10⁹+7.

Input

• The first line contains an integer T, the number of test cases. Then the test cases follow.
• The only line of each test case contains a single integer N.

Output

For each test case, output in a single line the answer to the problem modulo 10⁹+7.

Constraints

• 1≤T≤10⁵
• 1≤N≤10⁵

Subtasks

Subtask #1 (100 points): Original Constraints

Sample Input

2
1
2

Sample Output

1
2

Explanation

Test Case 1: The possible values of x are {0}.

Test Case 2: The possible values of x are {0,2}.

Code (Solution)

The code has been implemented in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
long n = sc.nextLong();
long count = findans(2,n-1,1000000007);
System.out.println(count);
}
}
public static long findans(long x, long y, long p){
//doing this for Modular Exponentiation to remove TLE
long res = 1;     // Initialize result
x = x%p;
if(x==0) return 0;
while (y > 0)
{
// If y is odd, multiply x with result
if ((y & 1) != 0)
res = (res * x)%p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x)%p;  // Change x to x^2
}
return res;
}
}

Hope you would have liked the article. Please give 50 claps to this article and follow me for more future programming related blogs.

References

https://www.codechef.com/MAY21C/problems/XOREQUAL