Find the Kth number which is not divisible by N | Python3 implementation for above approach ; Function to find the Kth not divisible by N ; Lowest possible value ; Highest possible value ; To store the Kth non divisible number of N ; Using binary search ; Calculating mid value ; Sol would have the value by subtracting all multiples of n till mid ; Check if sol is greater than k ; H should be reduced to find minimum possible value ; Check if sol is less than k then L will be mid + 1 ; Check if sol is equal to k ; ans will be mid ; H would be reduced to find any more possible value ; Print the answer ; Driver Code ; Function call
import sys NEW_LINE def kthNonDivisible ( N , K ) : NEW_LINE INDENT L = 1 NEW_LINE H = sys . maxsize NEW_LINE ans = 0 NEW_LINE while ( L <= H ) : NEW_LINE INDENT mid = ( L + H ) // 2 NEW_LINE sol = mid - mid // N NEW_LINE if ( sol > K ) : NEW_LINE INDENT H = mid - 1 NEW_LINE DEDENT elif ( sol < K ) : NEW_LINE L = mid + 1 NEW_LINE else : NEW_LINE INDENT ans = mid NEW_LINE H = mid - 1 NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT N = 3 NEW_LINE K = 7 NEW_LINE kthNonDivisible ( N , K ) NEW_LINE