Smallest divisor of N closest to X | Java program for the above approach ; Define macros ; Stores divisors for all numbers in the vector divisors ; i is the divisor and j is the multiple ; Function to compare the closeness of the given target ; Function to find the element closest to target in divisors vector ; Corner cases ; Perform binary search ; Check if target is less than the array element then search in left half ; Check if target is greater than previous to mid , return closest of two ; Repeat for left half ; Check if target is greater than mid ; Update i ; Only single element left after search ; Function to print the divisor of N closest to X ; Function call to calculate and stores divisors of all numbers in a vector ; Stores the closest value to target ; Print the answer ; Driver Code ; Given N & X ; Function Call
import java . util . * ; class GFG { static final int MAX = 10000 ; static Vector < Integer > [ ] divisors = new Vector [ MAX + 1 ] ; static void computeDivisors ( ) { for ( int i = 1 ; i <= MAX ; i ++ ) { for ( int j = i ; j <= MAX ; j += i ) { divisors [ j ] . add ( i ) ; } } } static int getClosest ( int val1 , int val2 , int target ) { if ( target - val1 >= val2 - target ) return val2 ; else return val1 ; } static int findClosest ( Vector < Integer > array , int n , int target ) { Integer [ ] arr = array . toArray ( new Integer [ array . size ( ) ] ) ; if ( target <= arr [ 0 ] ) return arr [ 0 ] ; if ( target >= arr [ n - 1 ] ) return arr [ n - 1 ] ; int i = 0 , j = n , mid = 0 ; while ( i < j ) { mid = ( i + j ) / 2 ; if ( arr [ mid ] == target ) return arr [ mid ] ; if ( target < arr [ mid ] ) { if ( mid > 0 && target > arr [ mid - 1 ] ) return getClosest ( arr [ mid - 1 ] , arr [ mid ] , target ) ; j = mid ; } else { if ( mid < n - 1 && target < arr [ mid + 1 ] ) return getClosest ( arr [ mid ] , arr [ mid + 1 ] , target ) ; i = mid + 1 ; } } return arr [ mid ] ; } static void printClosest ( int N , int X ) { computeDivisors ( ) ; int ans = findClosest ( divisors [ N ] , divisors [ N ] . size ( ) , X ) ; System . out . print ( ans ) ; } public static void main ( String [ ] args ) { int N = 16 , X = 5 ; for ( int i = 0 ; i < divisors . length ; i ++ ) divisors [ i ] = new Vector < Integer > ( ) ; printClosest ( N , X ) ; } }