Last Updated on March 23, 2022 by Ria Pathak
CONCEPTS USED:
Binary Search
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
Given an array of
Nsize containing the positions ofNmagnets. 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 to1/d, wheredis the distance. Task is to find all the points along the linear line whereNet ForceisZeroNote: 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 0Can we use Binary Search here ?
Yes, for every consecutive pair we need to find a point in between the pair where
net forceof all magnets becomes 0. In order to find such pointBinary Searchwould be an efficient alternative to quickly search for the point inLogarithmic 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 Forcewill be0. - We will use this observation and run a loop for all such consecutive pairs. Inside this loop, for every pair we will perform
Binary Searchand keep searching for amidpoint, wherenet forcesof all magnets become0.
- As there are
Npoints, so we will haveN-1points forN-1consecutive pairs.
How is Binary Search so fast ?
Binary Searchis aDivide and Conqueralgorithm.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 Complexityislog2(N), where there areNelements 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.