How should I practice XOR Coloring?

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

Is XOR Coloring associated with Microsoft?

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

Problem · Bit Manipulation

XOR Coloring

Learn this problem

● Hard

MicrosoftOA

See Microsoft hiring insights

Problem statement

You are given an array A containing N integers. For each element, choose exactly one of three actions: color it white, color it black, or leave it uncolored.

Let x be the XOR of all white elements and y be the XOR of all black elements. A coloring is good when x and y are both positive and either x is a multiple of y or y is a multiple of x.

Two colorings are different if at least one indexed element receives a different choice. Return the number of good colorings modulo 1,000,000,007.

Function

countGoodColorings(A: int[]) → int

Examples

Example 1

A = [1,2]return = 2

Color 1 white and 2 black, or color 2 white and 1 black. The XOR values are 1 and 2, and 2 is a multiple of 1. These are the only good colorings.

Example 2

A = [3,5,7]return = 0

Checking all 27 assignments shows that no coloring produces two positive XOR values where either value is a multiple of the other.

Example 3

A = [2,3,9]return = 6

There are six good colorings. In each one, all three elements are colored and one color contains one element while the other contains the remaining two. Swapping black and white gives a distinct coloring.

Constraints

1 ≤ N ≤ 12
1 ≤ A[i] ≤ 100,000