Cerinta completa

An XOR operation on a list is defined here as the xor () of all its elements (e.g.: ).

The of set is defined here as the sum of the s of all non-empty subsets of known as . The set can be expressed as:

For example: Given set

  • The set of possible non-empty subsets is:

  • The of these non-empty subsets is then calculated as follows:
    =

Given a list of space-separated integers, determine and print .

For example, . There are three possible subsets, . The XOR of , of and of . The XorSum is the sum of these: and .

Note: The cardinality of powerset is , so the set of non-empty subsets of set of size contains subsets.

Function Description

Complete the xoringNinja function in the editor below. It should return an integer that represents the XorSum of the input array, modulo .

xoringNinja has the following parameter(s):

  • arr: an integer array

Input Format

The first line contains an integer , the number of test cases.

Each test case consists of two lines:
– The first line contains an integer , the size of the set .
– The second line contains space-separated integers .

Constraints



Output Format

For each test case, print its on a new line. The line should contain the output for the test case.

Sample Input 0

1
3
1 2 3

Sample Output 0

12

Explanation 0

The input set, , has possible non-empty subsets: .

We then determine the of each subset in :






Then sum the results of the of each individual subset in , resulting in and .

Sample Input 1

2
4
1 2 4 8
5
1 2 3 5 100

Sample Output 1

120
1648

Limbajul de programare folosit: java8

Cod:

//https://www.hackerrank.com/challenges/xoring-ninja
import java.io.*;

public class Solution {
    
    final static int MOD = 1000000007;
    
    public static void main(String[] args) throws IOException {
        StringBuffer sb = new StringBuffer();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //For each test case
        for(byte T = Byte.parseByte(br.readLine()); T > 0; --T){
            
            //Get input set
            final int[] A = new int[Integer.parseInt(br.readLine())];
            int N = 0;
            for(String a : br.readLine().split(" ")){
                A[N++] = Integer.parseInt(a);
            }
            
            //Get set bits
            int bits = 0;
            for(int i = 0; i < N; bits |= A[i++]){}
            
            //Get xorSum
            int xorSum = 0;
            final int x = powMod(2, N-1, MOD);
            for(byte i = 0; bits > 0; ++i){
                if((bits & 1) == 1){
                    xorSum = (int)((xorSum + (((long)x) << i)) % MOD);
                }
                bits >>= 1;
            }
            
            //Print output
            sb.append(xorSum + "\n");
        }
        System.out.print(sb);
    }
    
    private static int powMod(int b, int p, final int m){
        int v = 1;
        while(p > 0){
            if ((p & 1) == 1){
                v = (int)((1L*v*b) % m);
            }
            p >>= 1;
            b = (int)((1L*b*b) % m);
        }
        return v;
    }
}

Scor obtinut: 1.0

Submission ID: 464612950

Link challenge: https://www.hackerrank.com/challenges/xoring-ninja/problem

Xoring Ninja