Find the Kth number which is not divisible by N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void kthNonDivisible ( int N , int K ) { int L = 1 ; int H = INT_MAX ; int ans = 0 ; while ( L <= H ) { int mid = ( L + H ) / 2 ; int sol = mid - mid / N ; if ( sol > K ) { H = mid - 1 ; } else if ( sol < K ) { L = mid + 1 ; } else { ans = mid ; H = mid - 1 ; } } cout << ans ; } int main ( ) { int N = 3 ; int K = 7 ; kthNonDivisible ( N , K ) ; return 0 ; }