Magnetic Force Between Two Balls - Practice Coding Problems

Magnetic Force Between Two Balls - Problem

In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the i-th basket is at position[i]. Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

Input & Output

Example 1 — Basic Case

$ Input: position = [1,2,3,4,7], m = 3

› Output: 3

💡 Note: Place balls at positions 1, 4, and 7. The minimum distance between any two balls is min(|4-1|, |7-4|, |7-1|) = min(3, 3, 6) = 3.

Example 2 — Closer Positions

$ Input: position = [5,4,3,2,1,1000000000], m = 2

› Output: 999999999

💡 Note: Place balls at positions 1 and 1000000000. The distance between them is |1000000000 - 1| = 999999999, which is the maximum possible minimum distance.

Example 3 — All Balls Must Fit

$ Input: position = [1,2,8,4,9], m = 4

› Output: 1

💡 Note: After sorting positions = [1,2,4,8,9]. To place 4 balls, we can place them at positions 1, 2, 4, 8 with minimum distance = 1.

Constraints

2 ≤ n ≤ 10⁵
1 ≤ m ≤ n
1 ≤ position[i] ≤ 10⁹
All position[i] are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

Array of basket positions and number of balls to place

Process

Find optimal placement to maximize minimum distance

Output

Maximum possible minimum distance

Key Takeaway

🎯 Key Insight: Use binary search on the answer space - if we can achieve distance X, we can achieve any smaller distance

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use binary search on the answer space. We can sort positions and use greedy placement to check if a given minimum distance is achievable. Best approach is Binary Search on Answer with Time: O(n log n + n log(max_pos)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(C(n,m) × m²)	O(m)	Generate all possible ways to place m balls and find the one with maximum minimum distance
Binary Search on Answer Space	O(n log n + n log(max_pos))	O(1)	Binary search on the possible minimum distance values, checking if each distance is achievable

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all combinations of m positions from n available positions
Step 2: For each combination, calculate minimum distance between any two balls
Step 3: Return the maximum of all minimum distances found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Combinations

Create all possible ways to choose m positions

Calculate Min Distance

For each combination, find minimum distance between balls

Keep Maximum

Track the combination with largest minimum distance

Code -

solution.c — C

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

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int countBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int solution(int* position, int n, int m) {
    int maxMinForce = 0;
    
    // Generate all combinations using bit manipulation
    for (int mask = 0; mask < (1 << n); mask++) {
        if (countBits(mask) != m) continue;
        
        int combo[20]; // Assuming max 20 positions
        int comboSize = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                combo[comboSize++] = position[i];
            }
        }
        
        // Find minimum distance in this combination
        int minForce = INT_MAX;
        for (int i = 0; i < comboSize; i++) {
            for (int j = i + 1; j < comboSize; j++) {
                int force = abs_val(combo[i] - combo[j]);
                if (force < minForce) {
                    minForce = force;
                }
            }
        }
        
        if (minForce > maxMinForce) {
            maxMinForce = minForce;
        }
    }
    
    return maxMinForce;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int position[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            position[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int m;
    scanf("%d", &m);
    
    int result = solution(position, n, m);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(n,m) × m²)

C(n,m) combinations, each requiring O(m²) comparisons to find minimum distance

✓ Linear Growth

Space Complexity

O(m)

Store current combination of m positions

✓ Linear Space

28.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

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler