Tuesday, May 30, 2023
HomeSoftware EngineeringClosest pair of factors in linearithmic time in Java

# Closest pair of factors in linearithmic time in Java

## The problem#

Given quite a lot of factors on a aircraft, your process is to search out two factors with the smallest distance between them in linearithmic O(n log n) time.

### Instance#

``````  1  2  3  4  5  6  7  8  9
1
2    . A
3                . D
4                   . F
5             . C
6
7                . E
8    . B
9                   . G
``````

For the aircraft above, the enter might be:

``````[
[2,2], // A
[2,8], // B
[5,5], // C
[6,3], // D
[6,7], // E
[7,4], // F
[7,9]  // G
]
=> closest pair is: [[6,3],[7,4]] or [[7,4],[6,3]]
(each solutions are legitimate)
``````

The 2 factors which are closest to one another are D and F.
Anticipated reply needs to be an array with each factors in any order.

### Objective#

The purpose is to provide you with a perform that may discover two closest factors for any arbitrary array of factors, in a linearithmic time.

`Level` class is preloaded for you as:

``````public class Level {
public double x, y;

public Level() {
x = y = 0.0;
}

public Level(double x, double y) {
this.x = x;
this.y = y;
}

@Override
public String toString() {
return String.format("(%f, %f)", x, y);
}

@Override
public int hashCode() {
return Double.hashCode(x) ^ Double.hashCode(y);
}

@Override
public boolean equals(Object obj) {
if (obj instanceof Level) {
Level different = (Level) obj;
return x == different.x && y == different.y;
} else {
return false;
}
}
}
``````

Extra info on wikipedia.

## The answer in Java code#

Possibility 1:

``````import java.util.*;
import java.lang.*;

public class Resolution {
public static Record<Level> closestPair(Record<Level> factors) {
remaining Record<Level> pair = new ArrayList<Level>();
remaining Record<Level> arr = new ArrayList<>(factors);
arr.type((a, b) -> Double.valueOf(a.x).compareTo(Double.valueOf(b.x)));
remaining int n = factors.measurement();
double l = Double.valueOf(Integer.MAX_VALUE);
double tolerance = Math.sqrt(l);
int a = 0, b = 0;
for (int i = 0; i + 1 < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr.get(j).x >= arr.get(i).x + tolerance) break;
remaining double ls = Math.pow(arr.get(i).x - arr.get(j).x, 2) + Math.pow(arr.get(i).y - arr.get(j).y, 2);
if (ls < l) {
l = ls;
tolerance = Math.sqrt(l);
a = i;
b = j;
}
}
}
return pair;
}
}
``````

Possibility 2:

``````import java.util.Arrays;
import java.util.*;
import java.util.stream.Collectors;

public class Resolution {

public static Record<Level> closestPair(Record<Level> factors) {
return divideAndConquer(factors.stream().sorted((o1, o2) -> Double.evaluate(o1.x,o2.x))
.acquire(Collectors.toList()).toArray(new Level[points.size()]),factors.measurement());
}
non-public static Record<Level> divideAndConquer(Level[] pointSet, int measurement){

if(measurement<=3){
double minDist=Double.MAX_VALUE;
Level aMin = null;
Level bMin = null;
for(int i=0; i<size-1;i++){
Level a = pointSet[i];
for(int j=i+1; j<measurement; j++){
Level b =  pointSet[j];
double dist = Math.abs(a.x-b.x)+Math.abs(a.y-b.y);
if(dist<minDist ){
minDist=dist;
aMin = a;
bMin = b;
}
}
}
return Arrays.asList(aMin,bMin);
}

int mid = measurement/2;

Level midPoint = pointSet[mid];

Record<Level> lMinPoints = divideAndConquer(Arrays.copyOfRange(pointSet, 0, mid), mid);
Record<Level> rMinPoints = divideAndConquer(Arrays.copyOfRange(pointSet, mid, measurement), size-mid);

double mDistL = calculateDist(lMinPoints.get(0),lMinPoints.get(1));
double mDistR = calculateDist(rMinPoints.get(0),rMinPoints.get(1));
Level aMin = null;
Level bMin = null;
double minDist;
if(mDistL<mDistR){
minDist = mDistL;
aMin = lMinPoints.get(0);
bMin = lMinPoints.get(1);
} else{
minDist = mDistR;
aMin = rMinPoints.get(0);
bMin = rMinPoints.get(1);
}
double streamMinDist = minDist;
Level[] midSetSorted = Arrays.stream(pointSet).filter(level -> Math.abs(midPoint.x-point.x)<streamMinDist)
.sorted((o1, o2) -> Double.evaluate(o1.y,o2.y)).toArray(Level[]::new);

if(midSetSorted.size==0){
return Arrays.asList(aMin,bMin);
}
for(int i=0; i<midSetSorted.length-1; i++){
Level level = midSetSorted[i];
for(int j=i+1; j<midSetSorted.size &&  Math.abs(midSetSorted[j].y - level.y) < minDist; j++){
if(calculateDist(midSetSorted[i],midSetSorted[j])<minDist){
minDist = calculateDist(midSetSorted[i],midSetSorted[j]);
aMin = midSetSorted[j];
bMin = midSetSorted[i];
}
}
}
return Arrays.asList(aMin,bMin);
}

non-public static double calculateDist(Level a, Level b){
return Math.abs(a.x-b.x)+Math.abs(a.y-b.y);
}
}
``````

## Check circumstances to validate our resolution#

``````import java.util.Arrays;
import java.util.Comparator;
import java.util.Record;

import org.junit.Assert;
import org.junit.FixMethodOrder;
import org.junit.Check;
import org.junit.runners.MethodSorters;

@FixMethodOrder(MethodSorters.NAME_ASCENDING)
public class SolutionTest {

@Check
public void test01_Example() {

Record<Level> factors = Arrays.asList(
new Level(2, 2), //A
new Level(2, 8), //B
new Level(5, 5), //C
new Level(6, 3), //D
new Level(6, 7), //E
new Level(7, 4), //F
new Level(7, 9)  //G
);

Record<Level> consequence = Resolution.closestPair(factors);
Record<Level> anticipated = Arrays.asList(new Level(6, 3), new Level(7, 4));
confirm(anticipated, consequence);
}

@Check
public void test02_TwoPoints() {

Record<Level> factors = Arrays.asList(
new Level(2, 2),
new Level(6, 3)
);

Record<Level> consequence = Resolution.closestPair(factors);
Record<Level> anticipated = Arrays.asList(new Level(6, 3), new Level(2, 2));
confirm(anticipated, consequence);
}

@Check
public void test03_DuplicatedPoint() {

Record<Level> factors = Arrays.asList(
new Level(2, 2), //A
new Level(2, 8), //B
new Level(5, 5), //C
new Level(5, 5), //C
new Level(6, 3), //D
new Level(6, 7), //E
new Level(7, 4), //F
new Level(7, 9)  //G
);

Record<Level> consequence = Resolution.closestPair(factors);
Record<Level> anticipated = Arrays.asList(new Level(5, 5), new Level(5,5));
confirm(anticipated, consequence);
}

non-public void confirm(Record<Level> anticipated, Record<Level> precise)
}
``````
RELATED ARTICLES