Balancing the Magnets

CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given an array of N size containing the positions of N 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, where d is the distance. Task is to find all the points along the linear line where Net Force is Zero

Note: Distance have to be calculated with the precision of 0.0000000000001.

See original problem statement here

For Example:

Input : arr = [4, 5]

Output : 4.5

Explanation : At point 4.5 both forces are equally repelling each other.
Input : arr = [5, 6, 7, 8]

Output : 5.38 6.50 7.62

Explanation : 

Between points 5 and 6, 5.38 is the point where net force of all magnets is 0

Between points 6 and 7, 6.50 is the point where net force of all magnets is 0

Between points 7 and 8, 7.62 is the point where net force of all magnets is 0

Can we use Binary Search here ?

Yes, for every consecutive pair we need to find a point in between the pair where net force of all magnets becomes 0. In order to find such point Binary Search would be an efficient alternative to quickly search for the point in Logarithmic Time Complexity.

SOLVING APPROACH:

  1. The idea is to learn programming languages online to use Binary Search.
  2. It is quite observatory fact that for every pair of consecutive elements there will be a point between them where Net Force will be 0.
  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 and keep searching for a mid point, where net forces of all magnets become 0.

  1. As there are N points, so we will have N-1 points for N-1 consecutive pairs.

How is Binary Search so fast ?

  • Binary Search is a Divide and Conquer algorithm.

  • 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.

  • Since half of the elements are eliminated in each check, its Time Complexity is log2(N), where there are N elements in the sorted array.

SOLUTIONS:


#include <stdio.h>
#include <stdlib.h>

//used to calculate force acting on a point
double force(int arr[],int n, double mid){

    double force = 0.0;
    for(int i = 0; i < n ; i++){
        force += 1/(mid-arr[i]);
    }
    return force;
}

double solution(int n, int arr[], double st, double end){
    double mid = (st + end)/2.0;
    double force_ = force(arr,n, mid);

    /* if force becomes equal or nearly equal to zero
 fabs() is used for finding absolute values of float and double */
    if(fabs(force_) <= 0.0000000000001){
            return mid;
    }

    //if force is greater than 0
    if(force_ > 0){
        return solution(n, arr, mid , end);
    }
    //if force is less than 0
    else
    {
        return solution(n, arr, st, mid);
    }
} 

int main()
{
  int t; scanf("%d", &t);
  while(t--){
      int n; scanf("%d", &n);
      int arr[n];
      for(int i = 0; i < n ; i++){
        scanf("%d", &arr[i]); 
      }
      //we will calculate points between each consecutive pairs
      for(int i = 0 ; i < n-1 ; i++){
          printf("%0.2f ", solution(n, arr, arr[i], arr[i+1]));
      }
      printf("\n");
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

//used to calculate force acting on a point
double force(int arr[],int n, double mid){

    double force = 0.0;
    for(int i = 0; i < n ; i++){
        force += 1/(mid-arr[i]);
    }
    return force;
}

double solution(int n, int arr[], double st, double end){
    double mid = (st + end)/2.0;
    double force_ = force(arr,n, mid);

    //if force becomes equal or nearly equal to zero
    if(abs(force_) < 0.0000000000001){
            return mid;
    }

    //if force is greater than 0
    if(force_ > 0){
        return solution(n, arr, mid , end);
    }
    //if force is less than 0
    else
    {
        return solution(n, arr, st, mid);
    }
} 

int main()
{
  int t; cin>>t;
  while(t--){
      int n; cin>>n;
      int arr[n];
      for(int i = 0; i < n ; i++){
        cin>>arr[i]; 
      }
      //we will calculate points between each consecutive pairs
      for(int i = 0 ; i < n-1 ; i++){
          cout<<fixed<<setprecision(2)<<solution(n, arr, arr[i], arr[i+1])<<" ";
      }
      cout<<"\n";
  }
  return 0;
}

import java.util.*;
import java.io.*;

import java.util.Scanner;

public class Main {

     //used to calculate force acting on a point
    private static double force(int[] arr, double mid){
        double force = 0.0;
        for(int i = 0; i < arr.length ; i++){
            force += 1.0/(mid-arr[i]);
        }
        return force;
    }

    private static double solution(int n, int[] arr, double st, double end){
        double mid = (st + end)/2.0;
        double force = force(arr, mid);

        //if force becomes equal or nearly equal to zero
        if(Math.abs(force) < 0.0000000000001){
                return mid;
        }
        //if force is greater than 0
        if(force > 0){
            return solution(n, arr, mid , end);
        }
        //if force is less than 0
        else
        {
            return solution(n, arr, st, mid);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int[] arr = new int[n];
            for(int i = 0; i < n ; i++){
                arr[i] = sc.nextInt();
            }
            //we will calculate points between each consecutive pairs
            for(int i = 0 ; i < n-1 ; i++){
                System.out.printf("%.2f" ,solution(n, arr, arr[i], arr[i+1]));
                System.out.print(" ");
            }
            System.out.println(" ");
        }
    }  
}

Space Complexity: O(1)

Previous post Transition Point
Next post Missing in AP

Leave a Reply

Your email address will not be published. Required fields are marked *