Last Updated on March 23, 2022 by Ria Pathak

### 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:

- The idea is to use
`Binary Search`

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

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

.

- 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)

[forminator_quiz id="1530"]

This article tried to discuss Binary Search. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.