Smallest divisor of N closest to X | Python3 program for the above approach ; 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
MAX = 10000 NEW_LINE divisors = [ [ ] for i in range ( MAX + 1 ) ] NEW_LINE def computeDivisors ( ) : NEW_LINE INDENT global divisors NEW_LINE global MAX NEW_LINE for i in range ( 1 , MAX + 1 , 1 ) : NEW_LINE INDENT for j in range ( i , MAX + 1 , i ) : NEW_LINE INDENT divisors [ j ] . append ( i ) NEW_LINE DEDENT DEDENT DEDENT def getClosest ( val1 , val2 , target ) : NEW_LINE INDENT if ( target - val1 >= val2 - target ) : NEW_LINE INDENT return val2 NEW_LINE DEDENT else : NEW_LINE INDENT return val1 NEW_LINE DEDENT DEDENT def findClosest ( arr , n , target ) : NEW_LINE INDENT if ( target <= arr [ 0 ] ) : NEW_LINE INDENT return arr [ 0 ] NEW_LINE DEDENT if ( target >= arr [ n - 1 ] ) : NEW_LINE INDENT return arr [ n - 1 ] NEW_LINE DEDENT i = 0 NEW_LINE j = n NEW_LINE mid = 0 NEW_LINE while ( i < j ) : NEW_LINE INDENT mid = ( i + j ) // 2 NEW_LINE if ( arr [ mid ] == target ) : NEW_LINE INDENT return arr [ mid ] NEW_LINE DEDENT if ( target < arr [ mid ] ) : NEW_LINE INDENT if ( mid > 0 and target > arr [ mid - 1 ] ) : NEW_LINE INDENT return getClosest ( arr [ mid - 1 ] , arr [ mid ] , target ) NEW_LINE DEDENT j = mid NEW_LINE DEDENT else : NEW_LINE INDENT if ( mid < n - 1 and target < arr [ mid + 1 ] ) : NEW_LINE INDENT return getClosest ( arr [ mid ] , arr [ mid + 1 ] , target ) NEW_LINE DEDENT i = mid + 1 NEW_LINE DEDENT DEDENT return arr [ mid ] NEW_LINE DEDENT def printClosest ( N , X ) : NEW_LINE INDENT global divisors NEW_LINE computeDivisors ( ) NEW_LINE ans = findClosest ( divisors [ N ] , len ( divisors [ N ] ) , X ) NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 16 NEW_LINE X = 5 NEW_LINE printClosest ( N , X ) NEW_LINE DEDENT