Xor Equality CodeChef Solution | Easy Approach | C++, Java, Python

Share:

Xor Equality CodeChef Solution Codechef

Xor Equality CodeChef Solution

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

Since the number of valid xx can be large, output it modulo 109+7109+7.

Input

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

Output

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

Constraints

  • 1≤T≤1051≤T≤105
  • 1≤N≤1051≤N≤105

Subtasks

Subtask #1 (100 points): Original Constraints

Sample Input

2
1
2

Sample Output

1
2

Solution

C++

#include <bits/stdc++.h>
#include <cstring>
#include <algorithm>
#define ll long long
#define min(a, b) ((a < b) ? a : b)
using namespace std;

int main()
{
    const int MID = 1e9 + 7;
    int a[100005];
    a[1] = 1;
    for (int i = 2; i < 100005; i++)
    {
        a[i] = (a[i - 1] * 2) % MID;
    }
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        cout << a[n] << endl;
    }
}

Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;


/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static int MX = 100005;
    public static int MOD = 1000000007;
    public static int[] ans = new int[MX];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scn = new Scanner(System.in);
		
		pre();
		int t = scn.nextInt();
		for(int i = 0; i < t; i++){
		    int n = scn.nextInt();
		    System.out.println(ans[n]);
		}
	}
	
	public static void pre(){
	    ans[1] = 1;
	    for(int i = 2; i < MX; i++){
	        ans[i] = (ans[i - 1] * 2) % MOD;
	    }
	}
}

Python

temp = (10**9)+7
t = int(input())
for i in range(t):
    n = int(input())
    ans = pow(2,(n-1),temp)
    print(ans)

Xor Equality CodeChef Solution Tutorial

See more posts here

Leave a Comment

Your email address will not be published. Required fields are marked *

x