Last Updated: 1 Mar, 2021
Magnet Array Problem
Easy
Asked in company
You have been given ‘N’ magnets which are placed linearly making a straight line. Each magnet experiences a repulsive force i.e magnets on the left repel to the right and magnets on the right repel to the left side. The force by which a magnet repels another magnet is equal to the reciprocal of the distance between them(1/d, where d is the distance between them).
You have been given an array “ARR” denoting the positions of the magnets on the x-axis, your task is to find all the equilibrium points on the x-axis.
Note :
An equilibrium point is a point where net force is 0 i.e repulsive force of left side magnets is equal to the repulsive force of right side magnets.
If there are N magnets, then there will be N - 1 equilibrium points.
The array “ARR” which denotes the positions of the magnets is in a sorted fashion.
For example :
If ARR = {1, 3} , then the output will be 2.
Explanation: For two points, the mid-point will have a net force of 0 because the distance from the mid-point will be equal.
Input Format :
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.
The first line of each test case contains an integer ‘N’ which denotes the number of magnets.
The second line of each test case contains ‘N’ space-separated integers denoting the positions of the magnets on the x-axis.
Output Format :
For each test case, print all the positions of zero net force with accuracy up to 3 decimal points.
Print the output of each test case in a separate line.
Constraints :
1 <= T <= 100
2 <= N <= 1000
0 <= ARR[i] <= 10000
Time Limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
The basic idea is to use binary search to find the equilibrium position.
As we can see the point of 0 force will lie between the coordinates of the pair magnets for which we are checking. In this way, there will be N - 1 such pair.
The searching of the point will be done with the help of a binary search, constantly changing the upper bound( initially the coordinate of the right magnet in the pair) and the lower bound( initially the position of the left magnet in the pair).
The force between two points is inversely proportional to the distance between the two points i.e Force = 1/(x - y) where ‘x’ and ‘y’ are the coordinates of the two points for which the force is to be calculated.
- For every pair, initialize “low” as ARR[i] and “high” as ARR[i+1].
- Declare “mid” as (“low” + “high”)/2 i.e mid point of the two magnets.
- Check if the total force at that point is 0 or not (Force is inversely proportional to the distance between the two points).
- So for calculating total force on a point, it will be equal to the sum of individual forces exerted by all magnets.
- If it is close to 0, it means the sum of force of left side magnets is approximately equal to sum of force of right side magnets, then that point is our equilibrium point.
- If it is greater than 0 it means that the forces exerted towards the right are greater than the forces exerted towards the left then again check for equilibrium point in the interval [ mid, high ].
- If it is less than 0 then move the search interval towards the left side i.e check in the interval [ low, mid ].
Similar problems