Find Original Array From Doubled Array - Practice Coding Problems

Find Original Array From Doubled Array - Problem

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array.

The elements in original may be returned in any order.

Input & Output

Example 1 — Basic Case

$ Input: changed = [1,3,4,2,6,8]

› Output: [1,3,4]

💡 Note: Original array [1,3,4] becomes [1,3,4,2,6,8] after doubling [2,6,8] and shuffling. We can recover [1,3,4] by pairing: 1↔2, 3↔6, 4↔8.

Example 2 — Impossible Case

$ Input: changed = [6,3,0,1]

› Output: []

💡 Note: Cannot form valid pairs. We have 6 but no 12, and 3 but no 6 available after pairing other elements.

Example 3 — With Zeros

$ Input: changed = [0,0,2,1]

› Output: [0,1]

💡 Note: Zeros pair with themselves: 0↔0, and 1↔2. Original array could be [0,1].

Constraints

1 ≤ changed.length ≤ 10⁵
0 ≤ changed[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Original Array

Start with array [1, 3, 4]

Double & Combine

Create [1, 3, 4, 2, 6, 8] then shuffle

Reverse Process

Find pairs and recover [1, 3, 4]

Key Takeaway

🎯 Key Insight: Sort first, then greedily pair each element with its double using frequency counting

Asked in

f Facebook 15 G Google 12 M Microsoft 8

The key insight is that each element in the original array must have exactly one corresponding doubled element. The frequency count approach is most intuitive - count elements, then process from smallest to largest, pairing each with its double. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Matching	O(n³)	O(n)	Try all possible pairings to find original elements
Frequency Count with Hash Map	O(n log n)	O(n)	Count frequencies, then greedily match elements with their doubles
Sort First Greedy	O(n log n)	O(n)	Sort array then greedily pair each element with its double

Brute Force Matching — Algorithm Steps

Iterate through each element
Find its pair (2x or x/2)
Mark both as used
Add to result if valid pairing exists

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Element

Pick first unused element

Search Pairs

Look for 2x or x/2 in remaining array

Mark Used

Remove both elements from consideration

Code -

solution.c — C

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

int* solution(int* changed, int changedSize, int* returnSize) {
    *returnSize = 0;
    if (changedSize % 2 != 0) return NULL;
    
    bool* used = (bool*)calloc(changedSize, sizeof(bool));
    int* original = (int*)malloc(changedSize / 2 * sizeof(int));
    int count = 0;
    
    for (int i = 0; i < changedSize; i++) {
        if (used[i]) continue;
        
        bool found = false;
        // Try to find double
        for (int j = i + 1; j < changedSize; j++) {
            if (!used[j] && changed[j] == changed[i] * 2) {
                used[i] = used[j] = true;
                original[count++] = changed[i];
                found = true;
                break;
            }
        }
        
        // Try to find half
        if (!found && changed[i] % 2 == 0) {
            for (int j = i + 1; j < changedSize; j++) {
                if (!used[j] && changed[j] == changed[i] / 2) {
                    used[i] = used[j] = true;
                    original[count++] = changed[j];
                    found = true;
                    break;
                }
            }
        }
        
        if (!found && !used[i]) {
            free(used);
            free(original);
            return NULL;
        }
    }
    
    *returnSize = count;
    free(used);
    return original;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int changed[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        changed[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(changed, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    if (result) free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each element O(n), search for pair O(n), mark as used O(n)

⚠ Quadratic Growth

Space Complexity

O(n)

Array to track used elements plus result array

⚡ Linearithmic Space

58.0K Views

Medium Frequency

~25 min Avg. Time

1.5K 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 Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler