CareerCup

sites.google.com/site/spaceofjameschen/home/search/find-a-number-in-the-array-having-least-difference-with-the-given-number-n----facebook
int FindNearestNum(int* arr, int len, int n)
{
if(len == 1) return arr[0];
if(n < arr[0]) return arr[0];
if(n > arr[len - 1]) return arr[len - 1];

int low = 0;
int up = len - 1;

while(low <= up){
int mid = low + (up - low) / 2;

if(arr[mid] == n){
return n;
}
else if(arr[mid] > n){
up = mid - 1;
}
else{
low = mid + 1;
}
}

return abs(arr[low] - n) > abs(arr[up] - n) ? arr[up] : arr[low];
}

This approach of binary search is considered as:
a. Find the middle element in the array. If the middle element is equal to the number then we have find our minimum difference of that number that is 0
b. If the number is less than the middle element then find the difference and then search further in the left half.
c. If the number is more than the middle element then find the difference and then search in the right half.
d. Here the variable difference is static for comparing this diff with other scenarios.
You can test this code below:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int leastDiff(int a[],int low,int high,int n)
{
    static int diff=INT_MAX;
    if(low>high)
    {
        return diff;
    }
    if(low==high)
    {
        if(a[low]>n)
        {
            int b=a[low]-n;
            if(b<diff)
                diff=b;
        }
        else
        {
            int b=n-a[low];
            if(b<diff)
                diff=b;
        }
        return diff;
    }
    else
    {
        int mid=low+(high-low)/2;
        if(a[mid]==n)
        {
            int b=a[mid]-n;
            if(b<diff)
                diff=b;
            return diff;
        }
        else if(a[mid]>n)//search in the left half to find min difference.
        {
            int b=a[mid]-n;
            if(b<diff)
                diff=b;
            leastDiff(a,low,mid-1,n);
            return diff;
        }
        else if(a[mid]<n)//search in the right half to find min difference
        {
            int b=n-a[mid];
            if(b<diff)
                diff=b;
            leastDiff(a,mid+1,high,n);
            return diff;
        }
    }
}
int main()
{
    int arr[]={10,20,30,40,50};
    int n=sizeof(arr)/sizeof(arr[0]);
    printf(" Minimum difference is %d ",leastDiff(arr,0,n-1,11));
}

First approach-
-if there is only one element return that element
-check if it is less than first element of array then return first element
-check if it is greater than the last element of the array then return last element
-if there are two elements return the nearest element
-else find the mid use modified binary search to return the nearest
O(lgn)
Second approach:
Can we use interval tree some how?
O(lgn)

O(log n) solution using Binary search notion :

#include <stdio.h>
#include <limits.h>

main() {
	int minEle, f, a[] = { 10, 14, 32, 49, 51, 62, 77 }, n = 7,i,j,mid,min = INT_MAX,ele;
	i = f = 0;
	j = n - 1;
	printf("Enter element : ");
	scanf("%d",&ele);
	printf("Nearest element is : ");
	while( i <= j ) {
		mid = (i+j)/2;
		if(a[mid] == ele)
		{
			f = 1;
			printf("%d\n",ele);
			break;
		}
		if( min > abs(a[mid]-ele) ) {
			min = abs(a[mid]-ele);
			minEle = a[mid];
		}
		if( a[mid] > ele)
			j = mid-1;
		else
			i = mid+1;
	}
	if( f == 0 )
		printf("%d\n",minEle);
}

for my solution every times array size is reduced to half

c++ code :

/*
Given - a number (n) and a sorted array
Find a number in the array having least difference with the given number (n)
*/

for( int i=0 ; i<n_array_size ; i++)
std::cin>>*( array_elementss + i );
for(int j=0 ; j<n_array_size ; j++ )#include<iostream>
using namespace std;
int Difference ( int temp1 , int temp2 ){
if( temp1 > temp2 ) return (temp1 - temp2 );
else return ( temp2 - temp1);
}
int Search( int *array_elements , int i_start_index , int i_end_index , int &i_middle, int &i_search){
int i_returnvalue;
i_middle= ( i_start_index + i_end_index ) / 2;
std::cout<<" middle = "<<i_middle<<std::endl;


int i_temp1=Difference ( * ( array_elements + i_middle ) , i_search );
//int i_temp2=Difference ( * ( aray_element + ( i_middle - 1) , i_search) );

if(i_temp1 ==0 )
return 0;
else {
if ( i_middle > i_start_index && i_middle < i_end_index ) {
int i_temp2=Difference ( * ( array_elements + ( i_middle - 1) ) , i_search) ;
int i_temp3= Difference ( * ( array_elements + ( i_middle + 1) ) , i_search ); std::cout<<"i_temp1 = "<<i_temp1<<"\n i_temp2= "<<i_temp2<<"\n i_temp3= "<<i_temp3<<std::endl;

if( i_temp2 < i_temp3){
if ( i_temp1 < i_temp2 )
return i_temp1;
else
Search ( array_elements , i_start_index , i_middle - 1 , i_middle , i_search );
}
else {
if ( i_temp1 < i_temp3 )
return i_temp1;
else{
std::cout<<"call\n";
Search ( array_elements , i_middle + 1 , i_end_index , i_middle , i_search ) ;
}
}
}

else{
std::cout<<i_start_index<<" " <<i_middle<<" "<<i_end_index<<std::endl;
if( i_middle == i_start_index & i_middle == i_end_index ) return ( Difference ( * (array_elements + i_middle ) , i_search ) );
else{


std::cout<<"call inside i_middle > start \n";
if ( i_middle > i_start_index ){

int i_temp2=Difference ( * ( array_elements + ( i_middle - 1 ) ) , i_search) ;
if ( i_temp1 < i_temp2 )
return i_temp1;
else
Search ( array_elements , i_start_index , i_middle - 1 , i_middle , i_search );
}
else
{
std::cout<<" call inside middle < end\n";
int i_temp3= Difference ( * ( array_elements + ( i_middle + 1) ) , i_search );
if ( i_temp1 < i_temp3 )
return i_temp1;
else
Search ( array_elements , i_middle + 1 , i_end_index , i_middle , i_search ) ;
}
}
}
// std::cout<<i_middle;
// return 1;

}
}

int main(){
int n_array_size , middle , i_search, i_temp1, i_temp2;
std::cin>>n_array_size;
std::cin>>i_search;
int *array_elementss=new int[ n_array_size ];
std::cout<< *( array_elementss + j )<<std::endl;
int i_result=Search( array_elementss , 0 , n_array_size - 1 , middle ,i_search);
std::cout<<"Result is :="<<i_result<<std::endl;

}

public static int findDifference(int [] array, int target){

int left=0;
int right=array.length-1;
int min=Integer.MAX_VALUE;
int value=array[0];
int rightVal=Integer.MAX_VALUE;
int leftVal=Integer.MAX_VALUE;;

while (left<=right){
int mid=(left+right);
if (array[mid]==target){
return array[mid];
}else if (target>array[mid]){
rightVal=Math.abs(target-array[mid]);
leftVal=Math.abs(target-array[right]);
if (rightVal<leftVal){
min=rightVal;
value=array[mid];
}else{
min=leftVal;
value=array[right];
}
left=mid+1;

}else{
rightVal=Math.abs(target-array[mid]);
leftVal=Math.abs(target-array[left]);
if (rightVal<leftVal){
min=rightVal;
value=array[mid];
}else{
min=leftVal;
value=array[left];
}
right=mid-1;
}
}

if (min>Math.abs(target-array[left])){
min=target-array[left];
value= array[left];
}

return value;

}

public static int findDifference(int [] array, int target){
		
		int left=0;
		int right=array.length-1;
		int min=Integer.MAX_VALUE;
		int value=array[0];
		int rightVal=Integer.MAX_VALUE;
		int leftVal=Integer.MAX_VALUE;;
		
		while (left<=right){
			int mid=(left+right);
			if (array[mid]==target){
		      return  array[mid];		
			}else if (target>array[mid]){
			  rightVal=Math.abs(target-array[mid]);
			  leftVal=Math.abs(target-array[right]);
			  if (rightVal<leftVal){
				  min=rightVal;
				  value=array[mid];
			  }else{
				  min=leftVal;
				  value=array[right]; 
			  }
			  left=mid+1;
				
			}else{
				  rightVal=Math.abs(target-array[mid]);
				  leftVal=Math.abs(target-array[left]);
				  if (rightVal<leftVal){
					  min=rightVal;
					  value=array[mid];
				  }else{
					  min=leftVal;
					  value=array[left];
				  }
				  right=mid-1;		
			}
		}
		
		if (min>Math.abs(target-array[left])){
			min=target-array[left];
			value= array[left];  
		}
		
		return value;

}

public class arrayElementDiff {
	public static void main(String[] args){
		int[]num = {1, 2, 4, 6, 7, 18, 21, 39, 43, 98, 154};
		int givenNum = 150;
		int left = 0, right = num.length, temp = 0, diff = 0, nearestNum = 0;
		diff = Math.abs(givenNum - num[left]);
		for (int i = 0; i < right; i++){
			temp = Math.abs(givenNum - num[left]);
			if (temp <= diff){
				nearestNum = num[i];
				diff = temp;
			}
			left++;
		}
		System.out.println ("Nearest = " + nearestNum);
	}
}

public class arrayElementDiff {
	public static void main(String[] args){
		int[]num = {1, 2, 4, 6, 7, 18, 21, 39, 43, 98, 154};
		int givenNum = 150;
		int left = 0, right = num.length, temp = 0, diff = 0, nearestNum = 0;
		diff = Math.abs(givenNum - num[left]);
		for (int i = 0; i < right; i++){
			temp = Math.abs(givenNum - num[left]);
			if (temp <= diff){
				nearestNum = num[i];
				diff = temp;
			}
			left++;
		}
		System.out.println ("Nearest = " + nearestNum);
	}
}

int ceil = upper_bound(a, n); // lowest i such that a[i] >= n
int floor = lower_bound(a, n); // highest i such that a[i]<=n
if ( floor == -1 )  return ceil
if (ceil == -1) return floor
else 
        return ceil - n <= n-floor ? ceil : floor;

public static int FindClosetNumber(int from, int to,int r1,int r2){
			if(from==to){
				if(sortedArray[from]==n)
					return sortedArray[from];
				if(n-r1 < r2-n)
					if(r1<sortedArray[0])
						return sortedArray[0];
					else
						return r1;
				else
					if(r2>sortedArray[sortedArray.length-1])
						return sortedArray[sortedArray.length-1];
					else
						return r2;
			}
			else{
				int mid = (int)(from+to)/2;
				if(sortedArray[mid]==n)
					return sortedArray[mid];
				else if (n<sortedArray[mid])
					return FindClosetNumber(from, mid-1, r1, sortedArray[mid]);
				else
					return FindClosetNumber(mid+1, to, sortedArray[mid], r2);
			}
		}

void leastdiff()
{
int i,j,k,mid,low,high;
int sorted[100]={0};
int min_num=0;
int f_number=0;
int n=0;

printf("enter the number of elements in sorted array");
scanf("%d",&n);

for(i=0;i<n;i++)
scanf("%d",&sorted[i]);

printf("enter the number for which least diff is to be calculated");
scanf("%d",&f_number);

mid=n/2;
low=0;
high=n;

while(low<high)
{



if(sorted[mid]<f_number)
low=mid+1;
else
high=mid-1;

mid=(high+low)/2;
}


min_num=abs(sorted[mid]-f_number);



}


we can simply use the binary search with above code

void leastdiff()
{
int i,j,k,mid,low,high;
int	sorted[100]={0};
int min_num=0;
int f_number=0;
int n=0;

printf("enter the number of elements in sorted array");
scanf("%d",&n);

for(i=0;i<n;i++)
scanf("%d",&sorted[i]);

printf("enter the number for which least diff is to be calculated");
scanf("%d",&f_number);

mid=n/2;
low=0;
high=n;

while(low<high)
{



if(sorted[mid]<f_number)
low=mid+1;
else
high=mid-1;

mid=(high+low)/2;
}


 min_num=abs(sorted[mid]-f_number);



}

logn solution

/*

Given - a number (n) and a sorted i_array 
Find a number in the i_array having least difference with the given number (n).
Developed By :Suman roy
Email : email.suman.roy@gmail.com
*/
#include<iostream>
#include<stdlib.h>
using namespace std;
int Min( int data1 , int data2, int search){
	if ( data2 > data1 ){
	int k=data2-search;
	int l=search - data1;
	if ( k > l ) return data1;
	else return data2;
	}
	else {
		int k=data1-search;
		int l=search - data2;
		if ( k> l)return data2;
		else return data1;
	}
}
int mid;
int Search ( int * i_array , int i_start , int i_end , int& i_search ){
	mid= ( i_start + i_end ) / 2;
	if ( i_array [ mid ] == i_search ) return i_search;
	else {
		if (  mid  == 0 ) 
			return Min( i_array [mid ] , i_array [mid+1],i_search ); 
		if ( mid== i_end ) return Min ( i_array [ mid ] , i_array [ mid - 1 ] , i_search );
		if ( i_array[mid ] <=i_search & i_search<= i_array [ mid + 1] ) return Min( i_array [ mid] ,i_array [mid + 1], i_search );
		if( i_array [mid ] >=i_search & i_search >=i_array [ mid - 1 ]  )retUrn Min ( i_array [ mid ] , i_array [mid - 1 ] , i_search );
		 if( i_array [ mid ] >i_search ) Search ( i_array , i_start , mid-1 , i_search );
		 else Search ( i_array , mid+1 , i_end , i_search );
	}
}


int main(){
	int  i_array[]={2, 5 ,7 , 12 , 17 , 24 , 26 , 29};
	int i_array_size , i_search_no;
	i_array_size=8;
	std::cout<<"Enter search element \n";
	std::cin>>i_search_no;
	int i_start=0;
	std::cout<<Search( i_array , i_start , i_array_size - 1 , i_search_no );
	return 0;
}

My implementation in ruby:

#!/usr/bin/ruby
#

require 'pp'

array = [1,2,3,4,5,6,7,9,12,14,15,28,30,34,36,38,39,80]


def findMinDifference number, array

  def findRecursive number, array, index = 0 

    if number == array[array.length/2]
      return array.length/2 + index - 1 
    end

    if number <= array[array.length/2]  and number >= array[array.length/2-1]
      return array.length/2 + index - 1 
    end

    if array[array.length/2] > number
      findRecursive number, array[0...array.length/2], index
    else
      pp "right"
      findRecursive number, array[array.length/2..array.length], index + array.length/2
    end

  end

  index = findRecursive number,array

  (array[index] - number).abs < (array[index+1] - number).abs ? array[index] : array[index+1]

end

pp findMinDifference 31, array

Its a tricky question to use modified bunary search...here is my c++ code...

#include<iostream>
#include<cstdlib>
using namespace std;


int findmin(int *arr,int n,int size)
{
//int size=sizeof(*arr)/sizeof(int);
cout<<"size is "<<size<<endl;
if(arr[0]>n)return arr[0];
else if(arr[size-1]<n)return arr[size-1];
else
{
int low=0,high=size-1;
int mid=(low+high)/2;

while(low<=high)
{
if(arr[mid]==n || low==high)return arr[mid];
if(arr[mid]>n)high=mid-1;
else if(arr[mid]<n)low=mid+1;
mid=(low+high)/2;
}
}

}


int main()
{
int size=0;
cout<<"enter size of array\n";
cin>>size;
int* arr=new int[size];
for(int i=0;i<size;i++)
cin>>arr[i];
int n;
cout<<"enter the number n\n";
cin>>n;
cout<<findmin(arr,n,size)<<endl;
return 0;
}

public static int getLeastDifference(int[] arr, int dst){
int distance = Integer.MAX_VALUE;
int leastIndex = -1;
int start = 0, end = arr.length;
while (start <= end){
int medium = (start + end) / 2;
int dis = Math.abs(arr[medium] -dst);
if (dis == 0){
return arr[medium];
} else {
if (dis < distance){
distance = dis;
leastIndex = medium;
}
}
if (arr[medium] < dst){
start = medium + 1;
} else {
end = medium - 1;
}
}

return arr[leastIndex];
}

Hi, I am a beginner. I tried this very easily. Please Check it out:

#include<stdio.h>
#include<conio.h>
main()
{
int arr[5] = {5, 7, 12, 18, 25};
int m[5];
int i, n, d, k=0;

printf("Enter Number (n): ");
scanf("%d" ,&n);

for(i=0;i<=4;i++)                           // calculating Differences and taking out their modulus//
                 {
                        m[i] = arr[i] - n;
                        
                        if (m[i] < 0)
                           m[i]= -m[i];
                        else 
                        continue;
                        }
d = m[1];
for(i=0; i<=4; i++)                    // least number in the modulus array//
{
         if ( m[i]<= d )
            d = m[i];
         else
         continue;
         }    

for(i=0; i<=4; i++)                 
         {
               if(d == m[i])
                    k = i;
               else
               continue;
         }
printf("The number with least difference: %d", arr[k]);
getch();
}

It think the question is asking the Smallest value in the array that is larger than the given value. If so, it can be done in O(lg n) as:

int indx=-1;
	while(b<=e)
	{
		int m=b+((e-b)/2);
		if(a[m]>=val && (indx>m || indx==-1))
		{
			indx=m;
			e=m-1;
		}
		else
			b=m+1;
	}
	printf("%d %d\n",max,indx);

{{
public static void main(String[] args) {
int array[] = {1, 10, 20, 30, 40, 50, 60, 70, 80};
int length = 9;
int n = 54;
System.out.println(numberWithLeastDiff(array, length, n));

}

public static int numberWithLeastDiff(int array[], int length, int n) {
if (length == 0) return -1;
if (length == 1) return array[0];
if (n <= array[0]) return array[0];
if (n >= array[length-1]) return array[length-1];

int min = 0, max = length - 1;
while (max - min > 1) {
int middleValue = array[(max+min)/2];
if (n == middleValue) return middleValue;
else if (n < middleValue) {
max = (max + min) / 2;
}
else {
min = (max + min) / 2;
}
}

return Math.abs(array[min] - n) < Math.abs(array[max] - n) ? array[min] : array[max];
}
}}

int find(int A[], int n, int target)
{
	if (target <= A[0]) return A[0];
	if (target >= A[n - 1]) return A[n - 1];
	int left = 0, right = n - 1;
	int minDiff = INT_MAX, res;
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (A[mid] == target) return target;
		int diff = abs(A[mid] - target);
		if (diff < minDiff)
		{
			minDiff = diff;
			res = A[mid];
		}
		
		if (target < A[mid]) right = mid - 1;
		if (target > A[mid]) left = mid + 1;
	}
	if (abs(A[left] - target) < minDiff)
	{
		minDiff = abs(A[left] - target);
		res = A[left];
	}
	if (abs(A[right] - target) < minDiff)
	{
		minDiff = abs(A[right] - target);
		res = A[right];
	}
	return res;
}

int findLeastDiff(int A[], int n, int target)
{
	if (target < A[0]) return A[0];
	if (target > A[n - 1]) return A[n - 1];
	
	int left = 0, right = n - 1;
	while (left + 1 < right)
	{
		int mid = left + (right - left) / 2;
		if (A[mid] == target) return target;
		else if (A[mid] > target)
			right = mid;
		else
			left = mid;
	}
	return (abs(A[left] - target) < abs(A[right] - target))? A[left] : A[right];
}

The simplest solution is java is as below it is on lg(n) where n is the array length:

public static int findLeastDiff(int n, int arr[]) {
		int start = 0;
		int end = arr.length - 1;
		int mid = (end + start) / 2;
		while (end - start > 1 ) {
			int rightDiff = Math.abs(arr[mid] - n);
			int leftDiff = Math.abs(arr[mid - 1] - n);
			if (rightDiff < leftDiff) {
				start = mid;

			} else if (rightDiff > leftDiff) {
				end = mid;
			} else
				break;
			mid = (end + start) / 2;
		}
		return arr[mid];

	}

I said - we do a binary search for finding n, and when we are left with just 2 elements in the array we return the number with least difference with n.

1. Do Binary Search on that input number -- O(lgn)
2. find successor than that's the least difference and if successor is not found than find predecessor - O(lgn)

because least difference has to be elements besides it. --- O(1)

Total - O(lgn)

private static int findMinDifNum(int[] a, int n)
	{
		if (a.length == 1)
			return a[0];
		else if (a[0] > n)
		{
			return a[0];
		}
		else if (a[a.length-1] < n)
		{
			return a[a.length-1];
		}else if (a.length == 2)
		{
			return n - a[0] > a[1] - n ? a[1] : a[0];
		}
		int left = 0;
		int right = a.length - 1;
		int mid = 0;
		while (left <= right)
		{
			mid = (left + right) / 2;

			if (a[mid] < n)
				left = mid + 1;
			else if (a[mid] > n)
				right = mid - 1;
			else
				break;
		}
		if (left <= right)
			return a[mid];
		
		if (a[mid] < n)
		{
			return n-a[mid] > a[mid+1] - n ? a[mid+1] : a[mid];
		}
		else
		{
			return a[mid] - n > n - a[mid-1] ? a[mid-1] : a[mid];
		}
		
	}

Since the array is sorted, begin checking from the beginning and the end.
For each check find the difference with the number (n) and compare the absolute value of the differences.
If the left difference is more increment the left pointer.
If the right difference is more decrement the right pointer.
Store the minimum difference.
If in the next iteration, the minimum difference is more than the minimum difference so far,stop and return the last number.

Just do a binary search for n in the array. Get the number immediately lower and immediate larger. Pick the one closer to n.

apply binary search with the key as number n
1.if number n is found,return n
2.else
if low>0 && low<lengthof(array),x=a[low],else x=-1;//-1 is used as sentinel
if high>0 && high<lengthof(array),y=a[high],else y=-1;
if(abs(x-n)>abs(y-n))
return y;
else return x;

Insert those numbers in a BST and then insert the number given to u...so now calculate its difference between its root node (and leaf nodes if they exist)....whichever is the minimum value...that shud be the answer...must be done in O(logn) if m nt wrong ! :)