How should I practice Product of XOR of All Good Pairs?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Product of XOR of All Good Pairs associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Product of XOR of All Good Pairs

Microsoft● MediumOA

Problem statement

Given an array of size N, find the product of XOR of all good pairs in the array. A pair (A[i],A[j]) is called good only when 0 <= i < j < N. Since the product of good pairs might be too large, hence print product % 1e9+7.

Input Format

The first line of input contains T - number of test cases. The first line of each test case contains N - the size of the array. The second line of each test case contains the N elements.

Output Format

Print the product of XOR of all good pairs in the array.

Constraints 30 points 2 <= N <= 10^3

70 points 2 <= N <= 10^5

General Constraints 1 <= T <= 10 1 <= A[i] <= 3000

Function

productOfXOROfAllGoodPairs(A: int[]) → int

Examples

Example 1

A = [1, 2, 3, 7]return = 720

Example 1: (1^2) * (1^3) * (1^7) * (2^3) * (2^7) * (3^7) = 720

Example 2

A = [4, 3, 7]return = 84

Example 2: (4^3) * (4^7) * (3^7) = 84

Constraints

See above