Minimum Cost to Move Chips to The Same Position

Minimum Cost to Move Chips to The Same Position - Problem

We have n chips, where the position of the i-th chip is position[i]. We need to move all the chips to the same position.

In one step, we can change the position of the i-th chip from position[i] to:

position[i] + 2 or position[i] - 2 with cost = 0
position[i] + 1 or position[i] - 1 with cost = 1

Return the minimum cost needed to move all the chips to the same position.

Input & Output

Example 1 — Mixed Positions

$ Input: position = [1,2,3]

› Output: 1

💡 Note: Odd positions: 1,3 (count=2). Even positions: 2 (count=1). Move 1 chip from even to odd or vice versa, cost = min(2,1) = 1.

Example 2 — Same Parity

$ Input: position = [2,2,2,3,3]

› Output: 2

💡 Note: Even positions: 2,2,2 (count=3). Odd positions: 3,3 (count=2). Move 2 chips from odd to even positions, cost = min(3,2) = 2.

Example 3 — All Same Position

$ Input: position = [1,1000000000]

› Output: 1

💡 Note: One odd (1), one even (1000000000). Need to move 1 chip to change its parity, cost = min(1,1) = 1.

Constraints

1 ≤ position.length ≤ 100
1 ≤ position[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Chips at various positions [1,2,3]

Movement Rules

±2 costs 0 (preserves parity), ±1 costs 1 (changes parity)

Strategy

Move minority parity group to majority group

Key Takeaway

🎯 Key Insight: Only parity matters - count chips at even vs odd positions and move the smaller group

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is that moving by 2 preserves parity (even/odd nature) and costs 0, while moving by 1 changes parity and costs 1. Best approach is parity analysis - count chips at even vs odd positions and return the minimum. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Insight - Parity Analysis	O(n)	O(1)	Count chips at even vs odd positions, return minimum
Brute Force - Try All Target Positions	O(n²)	O(1)	Calculate cost for moving all chips to each possible position

Mathematical Insight - Parity Analysis — Algorithm Steps

Count chips at even positions
Count chips at odd positions
Return minimum of the two counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Group by Parity

Separate chips into even and odd positions

Key Insight

Moving by 2 is free and preserves parity

Result

Move minority group to majority group

Code -

solution.c — C

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

int solution(int* position, int n) {
    int evenCount = 0;
    int oddCount = 0;
    
    for (int i = 0; i < n; i++) {
        if (position[i] % 2 == 0) {
            evenCount++;
        } else {
            oddCount++;
        }
    }
    
    return evenCount < oddCount ? evenCount : oddCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int position[1000];
    int n = 0;
    
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        position[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int result = solution(position, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to count even and odd positions

✓ Linear Growth

Space Complexity

O(1)

Only using two counters

✓ Linear Space

25.0K Views

Medium Frequency

~10 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

Mathematical Insight - Parity Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler