Magnet array problem

image from GFG

Binary search is one of the most optimized search methods. It has thousands of applications. Some of the small applications might include searching the following vs follower list on Instagram to find people whom you follow and who don’t follow you back, autocompletion of searches in chrome and other browsers, etc.

Today we are going to look at a clever application of binary search algorithm by solving a problem called “The magnet array problem”.

Problem statement :

Magnet Array Problem | Practice | GeeksforGeeks

Given n Magnets which are placed linearly, with each magnet to be considered as of point object. Each magnet suffers force from its left-sided magnets such that they repel it to the right and vice versa. All forces are repulsive. The force being equal to the distance (1/d, d is the distance). Now given the positions of the magnets, the task to find all the points along the linear line where the net force is ZERO.
Note: Distance has to be calculated with a precision of 0.0000000000001.

Thinking approach :

Given an array of N positions, where at each position is a magnet. Since all the magnets are said to repel each other we need not consider attractive forces in our system of N magnets. The only force in the system is of repulsive nature. So there have to be some points where the net force experienced due to all magnets will be zero. So how to find these positions?

Since there are N magnets there will have to be exactly N-1 points where the net magnetic force will be zero. The net force at a particular point will be the sum of all the forces on that point by all the other N magnets. So each point will lie in between two magnets. Therefore making a total of N-1 positions.

So our job is now made simple, we just have to search for a point between every magnet pair where the force adds up to zero. This is where binary search comes into play. The searching of the point will be done with the help of a binary search constantly changing the upper bound( initially the position of the right magnet in the pair) and the lower bound( initially the position of the left magnet in the pair).

The next question which arises is how to shift the search space in this binary search application?

If the net force on a point is found to be greater than zero it means that the forces exerted towards the right are greater than the forces exerted towards the left. So to decrease the value of the net force to zero we have to decrease the force towards the right. To do that we must move the point towards the right as the distance and force are inversely proportional. Similarly, if the net force is less than zero then move the search space towards the left. If it is exactly zero then end the search and print the position.

Algorithm:

1. Define a function to calculate the net force at a particular point. This can be done as the definition of the function is given in the question(1/d, where d is the distance).
2. Take the required inputs
3. Traverse through the array and apply the binary search algorithm between two adjacent elements.
4. In the binary search algorithm, we fix a left and a right boundary and then calculate the middle value. We check the net force on the middle point.
5. If the net force on the middle point is greater than 0 then we move the search space towards the right.
6. If the net force on the middle point is less than 0 then we move the search space towards right.
7. If the net force is exactly zero we end the search and move on to find the next equilibrium position between the next pair.

Code:

The time complexity of the solution is O(nlogn) and the space complexity is O(n).

Hope this article helped in clearing your concepts of binary search algorithm.