Neighboring Bitwise XOR - Practice Coding Problems

Neighboring Bitwise XOR - Problem

A 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.

Specifically, for each index i in the range [0, n - 1]:

If i = n - 1, then derived[i] = original[i] ⊕ original[0].
Otherwise, derived[i] = original[i] ⊕ original[i + 1].

Given an array derived, your task is to determine whether there exists a valid binary array original that could have formed derived.

Return true if such an array exists or false otherwise.

A binary array is an array containing only 0's and 1's

Input & Output

Example 1 — Valid Case

$ Input: derived = [1,1,0]

› Output: true

💡 Note: Original array [0,1,0] produces derived [1,1,0]: 0⊕1=1, 1⊕0=1, 0⊕0=0

Example 2 — Invalid Case

$ Input: derived = [1,0,0]

› Output: false

💡 Note: No binary array can produce [1,0,0]. XOR sum = 1⊕0⊕0 = 1 ≠ 0

Example 3 — All Zeros

$ Input: derived = [0,0,0,0]

› Output: true

💡 Note: Original [0,0,0,0] works: all XOR operations yield 0

Constraints

1 ≤ derived.length ≤ 10⁵
derived[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given derived array [1,1,0]

Process

Check if valid original exists

Output

Return true/false

Key Takeaway

🎯 Key Insight: XOR sum of all derived values must be 0 for valid solution

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that XOR-ing all derived values must equal 0 for a valid original to exist. This works because each original value appears in exactly two derived positions, and XOR cancels out. Best approach uses XOR sum property in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Try All Combinations	O(n × 2ⁿ)	O(n)	Try all 2^n possible binary arrays to see if any produces the given derived array
XOR Sum Property	O(n)	O(1)	Use mathematical property that XOR sum of all derived values reveals validity

Try All Combinations — Algorithm Steps

Generate all 2^n possible binary arrays
For each array, compute derived values using XOR
Check if computed derived matches given derived

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n binary arrays

Test

Check if each produces given derived

Result

Return true if any works

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* derived, int n) {
    // Try all 2^n possible binary arrays
    for (int mask = 0; mask < (1 << n); mask++) {
        int* original = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            original[i] = (mask >> i) & 1;
        }
        
        // Check if this original produces the given derived
        bool valid = true;
        for (int i = 0; i < n; i++) {
            int expected;
            if (i == n - 1) {
                expected = original[i] ^ original[0];
            } else {
                expected = original[i] ^ original[i + 1];
            }
            
            if (expected != derived[i]) {
                valid = false;
                break;
            }
        }
        
        free(original);
        if (valid) {
            return true;
        }
    }
    
    return false;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,0,1] format
    int derived[20];
    int n = 0;
    char* ptr = strchr(line, '[');
    ptr++;
    
    while (*ptr && *ptr != ']') {
        if (*ptr >= '0' && *ptr <= '9') {
            derived[n++] = *ptr - '0';
        }
        ptr++;
    }
    
    bool result = solution(derived, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ)

2^n possible arrays, each taking O(n) time to verify

✓ Linear Growth

Space Complexity

O(n)

Space for current candidate array and derived computation

⚡ Linearithmic Space

13.1K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler