We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Magnetic Force Between Two Balls

Number: 1675

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Apple, Salesforce, Roblox

Problem Description

You are given an array of distinct basket positions and an integer m, representing the number of balls. The goal is to place the m balls in the baskets so that the minimum magnetic force between any two balls is as large as possible. The magnetic force between balls at positions x and y is |x - y|. You need to compute this maximum achievable minimum force.

Key Insights

  • Sort the basket positions to enable efficient checking.
  • Use binary search on the “answer” (the minimum force) rather than iterating over all possible forces.
  • For a given minimum force, use a greedy strategy to place balls sequentially, placing a ball whenever the distance from the last placed ball meets the minimum requirement.
  • Adjust the search boundaries based on whether the placement was possible.

Space and Time Complexity

Time Complexity: O(n log(max_position - min_position)) Space Complexity: O(1) (ignoring the space used by sorting in-place)

Solution

The solution starts by sorting the basket positions. Then, the maximum possible minimum force is determined using binary search. The binary search explores all possible force values between 1 and the difference between the maximum and minimum basket positions. For each candidate force, a helper function checks if it is possible to place m balls such that each ball is at least the candidate force apart. This greedy placement starts from the first basket and places subsequent balls only when the current basket’s position is at least the candidate force away from the last placed ball. Adjust the binary search boundaries based on whether the placement is possible or not, and finally, return the largest force for which placement is possible.

Code Solutions

# Python solution for Magnetic Force Between Two Balls
def maxDistance(position, m):
    # Sort the basket positions
    position.sort()
    
    # Function to check if we can place m balls with at least min_force between them
    def canPlace(min_force):
        count = 1  # First ball placed in the first basket
        last_position = position[0]
        # Try to place remaining m-1 balls
        for pos in position[1:]:
            if pos - last_position >= min_force:
                count += 1
                last_position = pos
                if count == m:  # All m balls placed successfully
                    return True
        return False
    
    # Binary search boundaries
    low, high = 1, position[-1] - position[0]
    best_force = 0
    
    while low <= high:
        mid = (low + high) // 2  # Candidate minimum force
        if canPlace(mid):
            best_force = mid  # mid is a possible answer, try to find a larger distance
            low = mid + 1
        else:
            high = mid - 1
    return best_force

# Example usage:
print(maxDistance([1,2,3,4,7], 3))  # Output should be 3
← Back to All Questions