Circular XOR Array Validation

MEDIUM20 pts

You are given a 0-indexed integer array called derived of length n. This array was computed from some hidden binary array called source (also of length n) using the following circular XOR transformation:

For each position i in the range [0, n-1]:

If i is the last index (i = n - 1), then derived[i] = source[i] ⊕ source[0] (wrapping around to the beginning)
Otherwise, derived[i] = source[i] ⊕ source[i + 1] (XOR with the next adjacent element)

Here, ⊕ represents the bitwise XOR operation.

Your task is to determine whether there exists any valid binary array source that could have produced the given derived array through this circular XOR transformation.

Note: A binary array is an array that contains only 0s and 1s.

Return true if such a valid source array exists, or false otherwise.

Example

Input

derived = [1,1,0]

Output

true

Explanation

A valid source array [0,1,0] can produce the derived array: • derived[0] = source[0] ⊕ source[1] = 0 ⊕ 1 = 1 • derived[1] = source[1] ⊕ source[2] = 1 ⊕ 0 = 1 • derived[2] = source[2] ⊕ source[0] = 0 ⊕ 0 = 0 Therefore, a valid source exists.

Example

Input

derived = [1,1]

Output

true

Explanation

A valid source array [0,1] can produce the derived array: • derived[0] = source[0] ⊕ source[1] = 0 ⊕ 1 = 1 • derived[1] = source[1] ⊕ source[0] = 1 ⊕ 0 = 1 Thus, a valid source exists.

Example

Input

derived = [1,0]

Output

false

Explanation

No valid binary source array exists that can produce this derived array through the circular XOR transformation. Any attempt to construct such an array leads to a contradiction.

Accepted0/0·0% Acceptance

Constraints

n == derived.length
1 ≤ n ≤ 10⁵
Each element in derived is either 0 or 1

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

derived =

[1,1,0]

Circular XOR Array Validation

Hints

Circular XOR Array Validation

Hints