Magnetic Force Between Two Balls

📋

Magnetic Force Between Two Balls

Edge cases:

</>

IDE

def maxDistance(position: list[int], m: int) -> int:public int maxDistance(int[] position, int m)int maxDistance(vector<int>& position, int m)function maxDistance(position, m)

def maxDistance(position, m):
    # Write your solution here
    pass

class Solution {
    public int maxDistance(int[] position, int m) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxDistance(vector<int>& position, int m) {
    // Write your solution here
    return 0;
}

function maxDistance(position, m) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Too large minimum distance (e.g., 4 instead of 3)Greedy check incorrectly assumes balls can be placed with larger distance without verifying placement count.✅ Implement greedy check that counts how many balls can be placed with given distance and adjust binary search accordingly.

Wrong: Too small minimum distance (e.g., 1 instead of 3)Binary search lower bound or greedy check logic is incorrect, causing premature termination.✅ Ensure binary search updates low and high bounds correctly based on greedy check results.

Wrong: Off-by-one errors in output (e.g., 3 instead of 2)Incorrect mid calculation or comparison in binary search loop.✅ Use mid = low + (high - low + 1) // 2 and adjust low/high based on feasibility to avoid infinite loops and off-by-one errors.

Wrong: Fails on large inputs or times outUsing brute force approach with O(n*d) complexity instead of binary search on answer space.✅ Implement binary search on answer space with O(n log d) complexity and greedy feasibility check.

Wrong: Incorrect output when m equals number of positionsGreedy check skips positions or does not handle placing balls at every position.✅ Ensure greedy check places balls at every position if needed and binary search range includes minimum gap.

✓

Test Cases

Focus on handling smallest and largest inputs correctly, including boundary values.

Watch out for common pitfalls like greedy traps and off-by-one errors in binary search.

Optimize your solution to O(n log d) using binary search on answer space and greedy feasibility checks.

t1_01basic

Input{"position":[1,2,3,4,7],"m":3}

Expected3

⏱ Performance - must finish in 2000ms

Place balls at positions 1, 4, and 7. The minimum distance is min(4-1=3,7-4=3) = 3, which is the largest possible.

💡 Think about binary searching the minimum distance between balls.

💡 Use a greedy check to verify if balls can be placed with at least a given distance.

💡 Binary search over distance range and use greedy placement to find max minimum distance.

Why it failed: Returned incorrect max minimum distance; likely failed to implement binary search or greedy check correctly. Fix by ensuring binary search mid is tested with a proper greedy placement function.

✓ Correctly finds the maximum minimum distance using binary search and greedy check.

t1_02basic

Input{"position":[5,10,15,20,25],"m":2}

Expected20

⏱ Performance - must finish in 2000ms

With 2 balls, placing at positions 5 and 25 yields the maximum minimum distance of 20.

💡 For m=2, the answer is the max distance between any two positions.

💡 Binary search range is from 1 to max(position) - min(position).

💡 Check if you can place 2 balls with at least mid distance by placing first ball at min position and next at earliest position >= last + mid.

Why it failed: Incorrect output likely due to not considering max distance as initial upper bound or incorrect greedy placement logic. Fix by sorting positions and correctly implementing binary search boundaries and greedy check.

✓ Correctly handles minimum number of balls and finds max distance.

t2_01edge

Input{"position":[1,2],"m":2}

Expected1

⏱ Performance - must finish in 2000ms

Only two positions and two balls; max minimum distance is the difference 1.

💡 Check the smallest input size with minimum balls.

💡 Binary search range is from 1 to position[-1] - position[0].

💡 Greedy check should place balls at positions 1 and 2 successfully with distance 1.

Why it failed: Fails on minimum input size; likely does not handle smallest input or boundary conditions correctly. Fix by ensuring binary search handles low range and greedy check places all balls.

✓ Handles minimum input size and balls correctly.

t2_02edge

Input{"position":[1,2,3,4,5],"m":5}

Expected1

⏱ Performance - must finish in 2000ms

All positions consecutive and m equals number of positions; minimum distance is 1.

💡 When m equals number of positions, minimum distance is smallest gap between consecutive positions.

💡 Check that greedy placement does not skip any positions.

💡 Binary search should find minimum distance 1 as maximum possible.

Why it failed: Fails to handle case where m equals number of positions; likely greedy check skips positions or binary search range incorrect. Fix by ensuring greedy check places balls at every position if needed.

✓ Correctly handles placing balls at every position with minimum distance 1.

t2_03edge

Input{"position":[1,1000000000],"m":2}

Expected999999999

⏱ Performance - must finish in 2000ms

Positions are very spread out; max minimum distance is the difference 999999999.

💡 Test large distance range for binary search.

💡 Ensure no integer overflow in distance calculations.

💡 Greedy check should place balls at positions 1 and 1000000000 with distance 999999999.

Why it failed: Fails on large distance range; likely integer overflow or incorrect binary search bounds. Fix by using appropriate data types and correct binary search implementation.

✓ Handles large distance ranges without overflow.

t2_04edge

Input{"position":[1],"m":1}

Expected0

⏱ Performance - must finish in 2000ms

Single position and one ball; minimum distance is 0 since only one ball placed.

💡 Check behavior when only one ball is to be placed.

💡 Minimum distance is zero because no pair exists.

💡 Ensure code handles m=1 gracefully.

Why it failed: Fails on single element input or m=1; likely does not handle trivial cases. Fix by returning 0 when m=1 or only one position.

✓ Correctly handles single ball or single position cases.

t3_01corner

Input{"position":[1,2,4,8,9],"m":3}

Expected3

⏱ Performance - must finish in 2000ms

Greedy trap test: placing balls greedily with too large distance may fail; correct max minimum distance is 3.

💡 Beware of greedy trap: placing balls too far apart may miss valid placements.

💡 Binary search with greedy check must verify feasibility for each mid distance.

💡 Adjust binary search boundaries carefully and verify placement count.

Why it failed: Fails greedy trap test by returning too large distance without verifying placement feasibility. Fix by implementing correct greedy check that counts balls placed and adjusts binary search accordingly.

✓ Correctly handles greedy trap by verifying placement feasibility.

t3_02corner

Input{"position":[1,3,5,7,9],"m":4}

Expected2

⏱ Performance - must finish in 2000ms

Off-by-one error test: correct max minimum distance is 2, not 3.

💡 Check off-by-one errors in binary search mid calculation.

💡 Ensure greedy check places exactly m balls or fewer to adjust search.

💡 Binary search should narrow down to correct max minimum distance.

Why it failed: Returns incorrect distance due to off-by-one error in binary search or greedy check. Fix by carefully handling mid calculation and placement count comparison.

✓ Correctly handles off-by-one in binary search and greedy check.

t3_03corner

Input{"position":[1,2,4,7,11],"m":3}

Expected4

⏱ Performance - must finish in 2000ms

Test for confusion between 0/1 knapsack and binary search: max minimum distance is 5.

💡 This problem requires binary search on answer space, not knapsack.

💡 Greedy check places balls at earliest positions satisfying distance.

💡 Do not confuse with subset sum or knapsack approaches.

Why it failed: Fails by using incorrect approach like knapsack or subset sum instead of binary search. Fix by implementing binary search on minimum distance with greedy feasibility check.

✓ Correctly uses binary search on answer space with greedy check.

t4_01performance

Input{"position":[1,10001,20001,30001,40001,50001,60001,70001,80001,90001,100001,110001,120001,130001,140001,150001,160001,170001,180001,190001,200001,210001,220001,230001,240001,250001,260001,270001,280001,290001,300001,310001,320001,330001,340001,350001,360001,370001,380001,390001,400001,410001,420001,430001,440001,450001,460001,470001,480001,490001,500001,510001,520001,530001,540001,550001,560001,570001,580001,590001,600001,610001,620001,630001,640001,650001,660001,670001,680001,690001,700001,710001,720001,730001,740001,750001,760001,770001,780001,790001,800001,810001,820001,830001,840001,850001,860001,870001,880001,890001,900001,910001,920001,930001,940001,950001,960001,970001,980001,990001,1000001],"m":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and spaced positions to test O(n log d) complexity within 2 seconds.

💡 Binary search on answer space runs in O(n log d) time.

💡 Greedy check runs in O(n) time per binary search iteration.

💡 Brute force O(n*d) will time out; optimize with binary search.

Why it failed: TLE due to brute force or inefficient approach; fix by implementing binary search on answer space with O(n log d) complexity.

✓ Efficient binary search and greedy check pass within time limit.

Practice

1. Given the following code for shipping packages with early stopping feasibility check, what is the final returned minimum capacity for weights = [3, 2, 2, 4, 1, 4] and days = 3?

def can_ship_early_stop(weights, days, capacity):
    day_count = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            if day_count > days:
                return False
            current_load = 0
        current_load += w
    return True

def ship_with_capacity_binary_search_early_stop(weights, days):
    left, right = max(weights), sum(weights)
    while left < right:
        mid = (left + right) // 2
        if can_ship_early_stop(weights, days, mid):
            right = mid
        else:
            left = mid + 1
    return left

print(ship_with_capacity_binary_search_early_stop([3,2,2,4,1,4], 3))

easy

A. 7

B. 6

C. 8

D. 9

Solution

1. Step 1: Trace feasibility check with mid=6

   Check if capacity=6 can ship in 3 days: Day 1: 3+2=5 (ok), next 2 would exceed 6, so day 2 starts Day 2: 2+4=6 (ok), next 1 would exceed 6, so day 3 starts Day 3: 1+4=5 (ok) All packages shipped in 3 days -> feasible.

2. Step 2: Binary search narrows capacity

   Try mid=5 (less than max weight 4, so invalid), mid=7 is next check, which is feasible. The minimal feasible capacity is 7.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimal capacity found by binary search is 7 [OK]

Hint: Trace feasibility with mid to find minimal capacity [OK]

Common Mistakes:

• Off-by-one in mid calculation
• Miscounting days in feasibility
• Forgetting to reset current_load

2. Consider the following Python code that finds the k-th smallest number in an m x n multiplication table. What is the output when m = 3, n = 3, and k = 5?

easy

A. 6

B. 4

C. 3

D. 5

Solution

1. Step 1: Trace countLessEqual for mid=4

   For mid=4, count = sum of min(3, 4//i): i=1 -> min(3,4)=3; i=2 -> min(3,2)=2; i=3 -> min(3,1)=1; total=6 ≥ k=5, so high=4.

2. Step 2: Trace countLessEqual for mid=3

   For mid=3, count = i=1 -> 3; i=2 -> 1; i=3 -> 1; total=5 ≥ k=5, so high=3.

3. Step 3: Trace countLessEqual for mid=2

   For mid=2, count = i=1 -> 2; i=2 -> 1; i=3 -> 0; total=3 < k=5, so low=3.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Output matches expected k-th smallest number 5 [OK]

Hint: Count function caps counts per row [OK]

Common Mistakes:

• Off-by-one in counting
• Not breaking early in countLessEqual

3. You are given a sorted array and a target value. You need to find the index where the target should be inserted to maintain the sorted order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that inserts the target at the first position where the next element is larger

B. Linear scan from the start to find the first element greater than or equal to the target

C. Dynamic programming that builds solutions for subproblems of smaller arrays

D. Binary search that repeatedly halves the search space to find the correct insertion index

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so searching can be optimized by halving the search space instead of scanning linearly.

2. Step 2: Identify the algorithm that efficiently finds insertion index

   Binary search divides the array repeatedly, guaranteeing O(log n) time, which is optimal compared to linear or DP approaches.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search is the classic approach for sorted array search problems [OK]

Hint: Sorted array + insertion -> binary search [OK]

Common Mistakes:

• Assuming greedy insertion is always optimal
• Confusing DP with binary search
• Using linear scan despite sorted input

4. Consider the following buggy code snippet for checking if arrival is possible on time. Which line contains the subtle bug that can cause incorrect feasibility results?

from math import ceil

def can_arrive(dist, hour, speed):
    total_time = 0.0
    for i in range(len(dist)):
        total_time += ceil(dist[i] / speed)
    total_time -= ceil(dist[-1] / speed)  # Adjust last segment
    total_time += dist[-1] / speed
    return total_time <= hour

medium

A. Line 5: total_time += ceil(dist[i] / speed)

B. Line 6: total_time -= ceil(dist[-1] / speed) # Adjust last segment

C. Line 4: for i in range(len(dist))

D. Line 7: total_time += dist[-1] / speed

Solution

1. Step 1: Analyze loop bounds

   The loop iterates over all segments including the last, adding ceil for all, which overestimates time for last segment.

2. Step 2: Identify correct approach

   Only the first n-1 segments should use ceil; the last segment should add exact division time without ceiling.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop should be for i in range(len(dist) - 1) [OK]

Hint: Last segment time must not be ceiled [OK]

Common Mistakes:

• Applying ceil to last segment
• Incorrect loop range including last segment

5. Suppose the problem is modified so that the traveler can reuse the same speed for multiple trips (i.e., multiple independent journeys with the same speed constraint). Which modification to the binary search approach is necessary to handle this scenario correctly?

hard

A. Perform binary search separately for each trip and take the maximum minimum speed

B. Use a single binary search over speed and check feasibility across all trips combined

C. Switch to a brute force linear search since binary search no longer applies

D. Use dynamic programming to store feasibility states for each trip and speed

Solution

1. Step 1: Understand the reuse scenario

   All trips must be completed at the same speed, so feasibility must be checked collectively.

2. Step 2: Adapt binary search feasibility check

   Perform binary search on speed and verify if all trips can be completed on time at that speed combined.

3. Step 3: Reject separate searches or brute force

   Separate searches ignore the single speed constraint; brute force is inefficient; DP is unnecessary.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Single binary search with combined feasibility check handles reuse [OK]

Hint: Single binary search with combined feasibility check [OK]

Common Mistakes:

• Binary searching each trip separately
• Switching to brute force unnecessarily