Soluție HackerRank pentru Xoring Ninja. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Xoring Ninja

Cerinta completa

An XOR operation on a list is defined here as the xor ([Expresie matematică indisponibilă în copia arhivată]) of all its elements (e.g.: [Expresie matematică indisponibilă în copia arhivată]).

The [Expresie matematică indisponibilă în copia arhivată] of set [Expresie matematică indisponibilă în copia arhivată] is defined here as the sum of the [Expresie matematică indisponibilă în copia arhivată]s of all non-empty subsets of [Expresie matematică indisponibilă în copia arhivată] known as [Expresie matematică indisponibilă în copia arhivată]. The set [Expresie matematică indisponibilă în copia arhivată] can be expressed as:

[Expresie matematică indisponibilă în copia arhivată]

For example: Given set [Expresie matematică indisponibilă în copia arhivată]

  • The set of possible non-empty subsets is: [Expresie matematică indisponibilă în copia arhivată]

  • The [Expresie matematică indisponibilă în copia arhivată] of these non-empty subsets is then calculated as follows:
    [Expresie matematică indisponibilă în copia arhivată] = [Expresie matematică indisponibilă în copia arhivată]

Given a list of [Expresie matematică indisponibilă în copia arhivată] space-separated integers, determine and print [Expresie matematică indisponibilă în copia arhivată].

For example, [Expresie matematică indisponibilă în copia arhivată]. There are three possible subsets, [Expresie matematică indisponibilă în copia arhivată]. The XOR of [Expresie matematică indisponibilă în copia arhivată], of [Expresie matematică indisponibilă în copia arhivată] and of [Expresie matematică indisponibilă în copia arhivată]. The XorSum is the sum of these: [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

Note: The cardinality of powerset[Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată], so the set of non-empty subsets of set [Expresie matematică indisponibilă în copia arhivată] of size [Expresie matematică indisponibilă în copia arhivată] contains [Expresie matematică indisponibilă în copia arhivată] 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 [Expresie matematică indisponibilă în copia arhivată].

xoringNinja has the following parameter(s):

  • arr: an integer array

Input Format

The first line contains an integer [Expresie matematică indisponibilă în copia arhivată], the number of test cases.

Each test case consists of two lines:
– The first line contains an integer [Expresie matematică indisponibilă în copia arhivată], the size of the set [Expresie matematică indisponibilă în copia arhivată].
– The second line contains [Expresie matematică indisponibilă în copia arhivată] space-separated integers [Expresie matematică indisponibilă în copia arhivată].

Constraints

[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]

Output Format

For each test case, print its [Expresie matematică indisponibilă în copia arhivată] on a new line. The [Expresie matematică indisponibilă în copia arhivată] line should contain the output for the [Expresie matematică indisponibilă în copia arhivată] test case.

Sample Input 0

1
3
1 2 3

Sample Output 0

12

Explanation 0

The input set, [Expresie matematică indisponibilă în copia arhivată], has [Expresie matematică indisponibilă în copia arhivată] possible non-empty subsets: [Expresie matematică indisponibilă în copia arhivată].

We then determine the [Expresie matematică indisponibilă în copia arhivată] of each subset in [Expresie matematică indisponibilă în copia arhivată]:
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]

Then sum the results of the [Expresie matematică indisponibilă în copia arhivată] of each individual subset in [Expresie matematică indisponibilă în copia arhivată], resulting in [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

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