Decode XORed Permutation - Practice Coding Problems

Decode XORed Permutation - Problem

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. For example, if perm = [1,3,2], then encoded = [2,1].

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

Input & Output

Example 1 — Basic Case

$ Input: encoded = [3,1]

› Output: [1,2,3]

💡 Note: If perm = [1,2,3], then encoded[0] = 1⊕2 = 3 and encoded[1] = 2⊕3 = 1, giving us [3,1]

Example 2 — Different Permutation

$ Input: encoded = [6,5,4,6]

› Output: [2,4,1,5,3]

💡 Note: The permutation [2,4,1,5,3] produces: [2⊕4, 4⊕1, 1⊕5, 5⊕3] = [6,5,4,6]

Example 3 — Minimum Size

$ Input: encoded = [2,1]

› Output: [1,3,2]

💡 Note: Smallest valid case: [1,3,2] gives [1⊕3, 3⊕2] = [2,1]

Constraints

3 ≤ n ≤ 10⁵
n is odd
encoded.length == n - 1
perm is a permutation of [1, 2, ..., n]

Visualization

Tap to expand

Understanding the Visualization

Input

Encoded array where encoded[i] = perm[i] ⊕ perm[i+1]

Process

Use XOR properties to reverse the encoding process

Output

Original permutation of numbers 1 to n

Key Takeaway

🎯 Key Insight: XOR is reversible - if A⊕B=C, then A=C⊕B, allowing us to decode the permutation step by step

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is using XOR properties: since XOR is reversible and we know the permutation contains all numbers 1 to n, we can calculate the total XOR and use the encoded array to find the first element. Best approach uses bit manipulation with XOR properties. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O(n!)	O(n)	Generate all permutations and check which one produces the given encoded array
XOR Properties Solution	O(n)	O(1)	Use XOR properties to find the first element, then decode the rest sequentially

Brute Force - Try All Permutations — Algorithm Steps

Step 1: Determine n = encoded.length + 1
Step 2: Generate all permutations of [1,2,...,n]
Step 3: For each permutation, compute encoded[i] = perm[i] XOR perm[i+1]
Step 4: Return the permutation whose encoding matches the input

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of [1,2,3]

Test Each One

For each permutation, compute XOR encoding

Find Match

Return the permutation that matches encoded array

Code -

solution.c — C

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

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int checkPermutation(int* perm, int* encoded, int n) {
    for (int i = 0; i < n - 1; i++) {
        if ((perm[i] ^ perm[i + 1]) != encoded[i]) {
            return 0;
        }
    }
    return 1;
}

void generatePermutations(int* perm, int* encoded, int* result, int n, int start, int* found) {
    if (*found) return;
    
    if (start == n) {
        if (checkPermutation(perm, encoded, n)) {
            for (int i = 0; i < n; i++) {
                result[i] = perm[i];
            }
            *found = 1;
        }
        return;
    }
    
    for (int i = start; i < n; i++) {
        swap(&perm[start], &perm[i]);
        generatePermutations(perm, encoded, result, n, start + 1, found);
        swap(&perm[start], &perm[i]);
    }
}

int* solution(int* encoded, int encodedSize, int* returnSize) {
    int n = encodedSize + 1;
    *returnSize = n;
    
    int* perm = (int*)malloc(n * sizeof(int));
    int* result = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        perm[i] = i + 1;
    }
    
    int found = 0;
    generatePermutations(perm, encoded, result, n, 0, &found);
    
    free(perm);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int encoded[100];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            encoded[size++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(encoded, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generating all n! permutations, each taking O(n) time to verify

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing one permutation and the result array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 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

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler