{"id":1512,"date":"2020-07-01T09:31:25","date_gmt":"2020-07-01T09:31:25","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1512"},"modified":"2022-03-23T11:31:01","modified_gmt":"2022-03-23T11:31:01","slug":"balancing-the-magnets","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/balancing-the-magnets\/","title":{"rendered":"Balancing the Magnets"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Binary Search<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array of N<\/code> size containing the positions of N<\/code> magnets. These magnets are repelling each other. The magnets on the left of a magnet repels it to the right and magnets on the right repels it to left. The force is equal to 1\/d<\/code>, where d<\/code> is the distance. Task is to find all the points along the linear line where Net Force<\/code> is Zero<\/code><\/p>\n

Note<\/strong>: Distance have to be calculated with the precision of 0.0000000000001<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : arr = [4, 5]\n\nOutput : 4.5\n\nExplanation : At point 4.5 both forces are equally repelling each other.<\/code><\/pre>\n
Input : arr = [5, 6, 7, 8]\n\nOutput : 5.38 6.50 7.62\n\nExplanation : \n\nBetween points 5 and 6, 5.38 is the point where net force of all magnets is 0\n\nBetween points 6 and 7, 6.50 is the point where net force of all magnets is 0\n\nBetween points 7 and 8, 7.62 is the point where net force of all magnets is 0<\/code><\/pre>\n
Can we use Binary Search<\/code> here ?<\/em><\/strong>  <\/p>\n
\n
Yes<\/strong>, for every consecutive pair we need to find a point in between the pair where net force<\/code> of all magnets becomes 0. In order to find such point Binary Search<\/code> would be an efficient alternative to quickly search for the point in Logarithmic Time Complexity<\/code>.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
    \n
  1. The idea is to use Binary Search<\/code>.<\/li>\n
  2. It is quite observatory fact that for every pair of consecutive elements there will be a point between them where Net Force<\/code> will be 0<\/code>.<\/li>\n
  3. We will use this observation and run a loop for all such consecutive pairs. Inside this loop, for every pair we will perform Binary Search<\/code> and keep searching for a mid<\/code> point, where net forces<\/code> of all magnets become 0<\/code>.<\/li>\n<\/ol>\n
    \n\n<\/p><\/blockquote>\n
      \n
    1. As there are N<\/code> points, so we will have  N-1<\/code> points for N-1<\/code> consecutive pairs.<\/li>\n<\/ol>\n
      How is Binary Search<\/code> so fast  ?<\/em><\/strong><\/p>\n
      \n
        \n
      • \n
        Binary Search<\/code> is a Divide and Conquer<\/code> algorithm.<\/p>\n<\/li>\n
      • \n
        Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.<\/p>\n<\/li>\n
      • \n
        Since half of the elements are eliminated in each check, its Time Complexity<\/code> is log2(N)<\/code>, where there are N<\/code> elements in the sorted array.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
        SOLUTIONS:<\/h4>\n
        \t\t\t\t\t\t