HackerRank: Closest Numbers
Sorting is often useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses also.
Challenge
Given a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.
https://codepair.hackerrank.com/paper/tf6UKwXx?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
private static void compute(int[] input){
List<Integer> result = new ArrayList<Integer>();
Arrays.sort(input);
int mindist = Integer.MAX_VALUE;
Set<Integer> indexes = new HashSet<Integer>();
int currdist;
for(int i = 0; i < input.length-1; i++){
currdist = input[i+1] - input[i];
if(currdist < mindist){
indexes = new HashSet<Integer>();
indexes.add(i);
mindist = currdist;
}
if(currdist == mindist){
indexes.add(i);
}
}
Iterator<Integer> it = indexes.iterator();
int next;
while(it.hasNext()){
next = it.next();
result.add(input[next]);
result.add(input[next+1]);
}
Collections.sort(result);
for(int k = 0; k < result.size(); k++){
System.out.print(result.get(k)+" ");
}
}
public static void main(String[] args) throws IOException{
int N;
String[] temp;
String line = "";
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
line = br.readLine();
N = Integer.parseInt(line);
line = br.readLine();
temp = line.split(" ");
input = new int[N];
for(int i = 0; i < N; i++){
input[i] = Integer.parseInt(temp[i]);
}
compute(input);
}
Sorting is often useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses also.
Challenge
Given a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.
https://codepair.hackerrank.com/paper/tf6UKwXx?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
private static void compute(int[] input){
List<Integer> result = new ArrayList<Integer>();
Arrays.sort(input);
int mindist = Integer.MAX_VALUE;
Set<Integer> indexes = new HashSet<Integer>();
int currdist;
for(int i = 0; i < input.length-1; i++){
currdist = input[i+1] - input[i];
if(currdist < mindist){
indexes = new HashSet<Integer>();
indexes.add(i);
mindist = currdist;
}
if(currdist == mindist){
indexes.add(i);
}
}
Iterator<Integer> it = indexes.iterator();
int next;
while(it.hasNext()){
next = it.next();
result.add(input[next]);
result.add(input[next+1]);
}
Collections.sort(result);
for(int k = 0; k < result.size(); k++){
System.out.print(result.get(k)+" ");
}
}
public static void main(String[] args) throws IOException{
int N;
String[] temp;
String line = "";
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
line = br.readLine();
N = Integer.parseInt(line);
line = br.readLine();
temp = line.split(" ");
input = new int[N];
for(int i = 0; i < N; i++){
input[i] = Integer.parseInt(temp[i]);
}
compute(input);
}