Magnetic Force Between Two Balls is a simple problem that can be solved using the binary search approach. Here we will discuss the approach and complexity of the algorithm.
Problem Statement
In-universe Earth C-137, Ninja discovered a special form of magnetic force between two balls if they are put in his newly invented basket. Ninja has n empty baskets; the ith basket is at position[i], Ninja has m balls that need to distribute into the baskets such that the minimum magnetic force between any two balls is to be maximized.
Ninja stated that the magnetic force between two different balls at positions x and y is |x - y|.
For given the integer array of positions and the integer m, return the required force.
Explanation: Distributing the 3 balls into baskets 1, 4, and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.
Method
We need to maximize the minimum difference between the adjacent balls to increase the force between the adjacent balls. So we will find the optimal difference using binary search and check if it is possible to keep this particular difference between the adjacent balls and keep updating the final answer to get the maximum.
We count the number of balls that can be placed into baskets under the condition that the minimum distance between any two balls is mid+1.
If the count >= m, possible solution to the right of mid. Else possible solution to the left of mid.
after an optimal search later we get the answer in l
int maxDistance(vector<int>& pos, int m) { sort(pos.begin(),pos.end()); int l=0,h=pos.back(); while(l<h){ intmid=l+(h-l)/2,pivot=-1e9,count=0; for(int a:pos) if(a-pivot>=mid+1){pivot=a;count++;} if(count>=m)l=mid+1; else h=mid; } return l; }
Code
// c++ code for magnetic-force-between-two-balls problem
#include<bits/stdc++.h> usingnamespacestd;
intmaxDistance(vector<int>& pos, int m) { sort(pos.begin(),pos.end()); int l=0,h=pos.back(); while(l<h){ int mid=l+(h-l)/2,pivot=-1e9,count=0; // count the number of balls that can be placed into //baskets, // under the condition that the minimum distance //between any two balls is mid+1. for(int a:pos) { if(a-pivot>=mid+1) { pivot=a; count++; } }
// If the count >= m, possible solution to the right // of mid.
if(count>=m)l=mid+1; //else possible solution to the left of mid else h=mid; } return l; }
// driver code
intmain() { vector<int> positions{1,2,3,4,7};
int m=3;
cout<<"The required force = "<<maxDistance(positions,m); }
Output
The required force = 3
Complexity
The above algorithm takes O(nlog n) time as we are sorting the given array of positions.
Clearly, space complexity is O(1) in this case, as no extra space is required.
FAQs
1). What is binary search?
Binary search is an effective algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the list into half portions of the list containing the item until we have narrowed down the possible locations to just one.
2). What is the time complexity of the binary search algorithm?
The time complexity of the binary search algorithm is O(log n), where n is the length of the sorted list.
3). What kind of sorting is used in the C++ STL sort() function?
It uses a hybrid sorting algorithm of insertion sort, heap sort, quicksort.
Key Takeaways
This article covered how to solve the problem of magnetic-force-between-two-balls and its c++ code.
Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.
Live masterclass
Master PowerBI using Netflix Data
by Ashwin Goyal, Product @ HRS Groups, Ex - Udaan, OYO
305+ registered