Minimum Number of Operations to Make Arrays Similar - Problem

You are given two positive integer arrays nums and target, of the same length.

In one operation, you can choose any two distinct indices i and j where 0 <= i, j < nums.length and:

set nums[i] = nums[i] + 2 and
set nums[j] = nums[j] - 2.

Two arrays are considered to be similar if the frequency of each element is the same.

Return the minimum number of operations required to make nums similar to target. The test cases are generated such that nums can always be similar to target.

Input & Output

Example 1 — Basic Case

$ Input: nums = [8,6,4,2], target = [6,4,8,2]

› Output: 1

💡 Note: We can make nums similar to target in one operation: transfer 2 from nums[0] to nums[1] to get [6,8,4,2], which has the same frequencies as target.

Example 2 — No Operations Needed

$ Input: nums = [1,2,3,4], target = [2,1,4,3]

› Output: 0

💡 Note: nums and target already have the same frequency of each element: one 1, one 2, one 3, one 4. No operations needed.

Example 3 — Multiple Operations

$ Input: nums = [1,1,1,1], target = [1,1,9,9]

› Output: 4

💡 Note: Need to convert two 1's to 9's. Each 1→9 requires 4 operations: 1→3→5→7→9. But we do it optimally by transferring from one element to another.

Constraints

n == nums.length == target.length
1 ≤ n ≤ 10⁵
1 ≤ nums[i], target[i] ≤ 10⁶
nums and target have the same sum

Visualization

Tap to expand

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that operations preserve parity - even numbers stay even, odd numbers stay odd. We separate numbers by parity, sort each group, and greedily match elements. The optimal approach uses greedy matching with time complexity O(n log n) and space complexity O(n).

Common Approaches

✓ Brute Force Simulation

⏱️ Time: O(2^n) Space: O(2^n)

Generate all possible states by applying operations and use BFS to find minimum steps. This approach simulates every possible combination of operations until we reach a state where nums has the same element frequencies as target.

Greedy Matching (Even/Odd Separation)

⏱️ Time: O(n log n) Space: O(n)

Since operations only change numbers by ±2, parity (even/odd) is preserved. We separate numbers into even and odd groups, sort them, and greedily match elements that need to increase with elements that need to decrease.

Brute Force Simulation — Algorithm Steps

Generate all possible operations for current state
Apply each operation and check if result matches target frequencies
Use BFS to explore states level by level
Return the minimum number of steps

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with nums array and target frequencies

Generate Operations

Try all i,j pairs: nums[i]+=2, nums[j]-=2

BFS Search

Explore all states until target frequency is reached

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize, int* target, int targetSize) {
    // Separate odd and even numbers
    int nums_odd[100], nums_even[100];
    int target_odd[100], target_even[100];
    int odd_count = 0, even_count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] % 2 == 1) {
            nums_odd[odd_count++] = nums[i];
        } else {
            nums_even[even_count] = nums[i];
            even_count++;
        }
    }
    
    int target_odd_count = 0, target_even_count = 0;
    for (int i = 0; i < targetSize; i++) {
        if (target[i] % 2 == 1) {
            target_odd[target_odd_count++] = target[i];
        } else {
            target_even[target_even_count] = target[i];
            target_even_count++;
        }
    }
    
    // Sort the arrays
    qsort(nums_odd, odd_count, sizeof(int), compare);
    qsort(nums_even, even_count, sizeof(int), compare);
    qsort(target_odd, target_odd_count, sizeof(int), compare);
    qsort(target_even, target_even_count, sizeof(int), compare);
    
    int operations = 0;
    
    // Calculate operations needed for odd numbers
    for (int i = 0; i < odd_count; i++) {
        int diff = abs(nums_odd[i] - target_odd[i]);
        operations += diff / 2;
    }
    
    // Calculate operations needed for even numbers
    for (int i = 0; i < even_count; i++) {
        int diff = abs(nums_even[i] - target_even[i]);
        operations += diff / 2;
    }
    
    // Each operation involves adding 2 to one number and subtracting 2 from another
    // So we need to divide by 2 to get the actual number of operations
    return operations / 2;
}

int parseArray(const char* str, int* arr) {
    int size = 0;
    int num = 0;
    int sign = 1;
    int reading = 0;
    
    for (int i = 0; str[i]; i++) {
        char c = str[i];
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
            reading = 1;
        } else if (c == '-') {
            sign = -1;
            reading = 1;
        } else if ((c == ',' || c == ']') && reading) {
            arr[size++] = num * sign;
            num = 0;
            sign = 1;
            reading = 0;
        }
    }
    return size;
}

int main() {
    char buffer[1000];
    
    // Read nums array
    fgets(buffer, sizeof(buffer), stdin);
    buffer[strcspn(buffer, "\n")] = 0;
    
    int nums[100];
    int numsSize = parseArray(buffer, nums);
    
    // Read target array
    fgets(buffer, sizeof(buffer), stdin);
    buffer[strcspn(buffer, "\n")] = 0;
    
    int target[100];
    int targetSize = parseArray(buffer, target);
    
    int result = solution(nums, numsSize, target, targetSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each element can be modified in many ways, leading to exponential states

⚡ Linearithmic

Space Complexity

O(2^n)

Need to store all possible states in BFS queue

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Minimum Number of Operations to Make Arrays Similar - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler