CareerCup

sort two arrays.

Is there any solution without sorting the array?

look for max and min element in array and stop as soon as difference between current found elements is 2 or more. complexity O(n).

find differnce between every pair possible and find minimum (without sorting array)

Here is sample programme to get the desired result.


package randomTest;

public class LeastDifferenceNumber {

private int[] numberArray = new int[50];

private void sortArray(){
if(numberArray !=null && numberArray.length>0){
for(int i=1;i<numberArray.length; i++){
int pos = i-1;
int temp = numberArray[i];
while(numberArray[pos]>temp){
numberArray[pos+1]= numberArray[pos];
pos--;
}
numberArray[pos+1]=temp;
}
}
}

private int getLeastDifferenceIndex(){
int leastDifferencePos = 1;
int minDiff = -1;
if(numberArray !=null && numberArray.length>0){
for(int i=1;i<numberArray.length; i++){
int diff=numberArray[i]-numberArray[i-1];
if(diff<minDiff){
minDiff = diff;
leastDifferencePos = i;
}
}
}
return leastDifferencePos;
}


/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LeastDifferenceNumber leastDifferenceNumber = new LeastDifferenceNumber();
leastDifferenceNumber.numberArray = new int []{1, 18, 22, 28, 8, 58, 22, 92};
leastDifferenceNumber.sortArray();
int leastDifferencePos = leastDifferenceNumber.getLeastDifferenceIndex();
System.out.println("Least Difference position is ->" + leastDifferenceNumber.numberArray[leastDifferencePos-1] + " and " + leastDifferenceNumber.numberArray[leastDifferencePos]);

}

}


Algorithm:
1) Sort the array.
2) Find the position of the two consecutive digits in array whose difference is lowest.

int main()
{
	int a[] = { 5, 6, 5, 4, 7 };
	int i, n = sizeof(a) / sizeof(int);
	int max, min;
	
	
	max = a[0];
	min = a[1]; 
	for (i = 2; i < n; ++i)
	{
		if(abs(max - min) > abs(max - a[i]))
		   min = a[i];
		if( abs(max - min) > abs(a[i] - min))
			max = a[i];
	}
	
	cout << "max = " << max << " min = " << min << endl; 

	
	return 0;
}

This problem is akin to bin packing. Its not as simple as finding the max and min of the given input list. Instead you pack every element into a bin and then find the pair with the least difference.

i) Find the bin size - (Max-min)/n. For the above given example, this would be (12-5)/5 = 1.39.
ii) Create n bins. Ex: bin1 - (min to min+bin_size), bin2 - (min+bin_size to min+bin_size*2)..so on. For the above given example, this would be bin1 (5-6.39), bin2(6.39-7.79)...bin5(10.6-12)
iii) Insert each element into its appropriate bin based on its range (lower_bound, upper bound]. Make an exception for the last bin.
iv) Exit the algorithm if any duplicates are found. Otherwise, find the difference between the max and min of each bin and between bins. Keep track and return the pair with the least difference.

Running time - O(n).