Array of Doubled Pairs - Practice Coding Problems

Array of Doubled Pairs - Problem

Given an integer array arr of even length, return true if it is possible to reorder arr such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2, or false otherwise.

In other words, we need to check if we can pair up all elements such that each pair contains a number and its double.

Input & Output

Example 1 — Basic Valid Case

$ Input: arr = [1,2,4,16,8,4]

› Output: true

💡 Note: We can reorder as [1,2,4,8,4,16] where arr[1]=2×arr[0], arr[3]=2×arr[2], arr[5]=2×arr[4]

Example 2 — Impossible Case

$ Input: arr = [2,1,2,6]

› Output: false

💡 Note: We have two 2s but only one 1 and one 6. We can pair (1,2) but the remaining 2 cannot pair with 6 since 6≠2×2

Example 3 — Zeros

$ Input: arr = [4,-2,2,-4]

› Output: true

💡 Note: We can pair (-2,-4) since -4 = 2×(-2) and (2,4) since 4 = 2×2

Constraints

1 ≤ arr.length ≤ 1000
arr.length is even
-1000 ≤ arr[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,4,16,8,4] needs to be paired

Find Pairs

Match each number with its double: (1,2), (4,8), (4,16)

Check Valid

All elements can be paired successfully

Key Takeaway

🎯 Key Insight: Count frequencies and greedily match each number with its double, handling zeros as special case

Asked in

G Google 42 f Facebook 28 a Amazon 35

The key insight is to count frequencies of each number and greedily match each with its double. Best approach is frequency counting which handles zeros and negatives correctly. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Try All Pairings	O(n!)	O(n)	Generate all possible ways to pair elements and check if any valid pairing exists
Sort and Greedy Pairing	O(n log n)	O(1)	Sort array and greedily pair each element with its double using two pointers
Frequency Count and Greedy Matching	O(n)	O(n)	Count frequency of each number and greedily match each with its double

Try All Pairings — Algorithm Steps

Generate all possible pairings of array elements
For each pairing, check if every pair (a,b) satisfies b = 2*a
Return true if any valid pairing is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Array

Start with array [1,2,4,16,8,4]

Try Pairing

Attempt different combinations: (1,2), (4,8), (4,16)

Check Valid

Verify each pair satisfies doubling condition

Code -

solution.c — C

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

bool backtrack(int* arr, int size, bool* used, int pairsFound) {
    if (pairsFound == size / 2) {
        return true;
    }
    
    for (int i = 0; i < size; i++) {
        if (used[i]) continue;
        for (int j = i + 1; j < size; j++) {
            if (used[j]) continue;
            
            if (arr[j] == 2 * arr[i] || arr[i] == 2 * arr[j]) {
                used[i] = used[j] = true;
                if (backtrack(arr, size, used, pairsFound + 1)) {
                    return true;
                }
                used[i] = used[j] = false;
            }
        }
        break;
    }
    
    return false;
}

bool solution(int* arr, int size) {
    bool* used = (bool*)calloc(size, sizeof(bool));
    bool result = backtrack(arr, size, used, 0);
    free(used);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(arr, size);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

We try all possible ways to pair n elements, which is factorial complexity

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth for backtracking

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 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 Pairings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler