878. Nth Magical Number Solution | LeetCode | Binary Search
Raunit Verma - in Leetcode
Views: 0
A positive integer is magical if it is divisible by either a or b. Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.
class Solution {
public:
const int MOD = 1e9+7;
bool helper(long long n, int a, int b, long long mid){
long long cnt = 0;
cnt+=(mid/a);
cnt+=(mid/b);
long long lcm = ((a*b)/(__gcd(a,b)));
cnt-=(mid/lcm);
return cnt>=n;
}
int nthMagicalNumber(int n, int a, int b) {
long long low = 1, mid, high = 1e18;
while(high>=low){
mid = low + (high-low)/2;
if(helper(n,a,b,mid)){
high = mid-1;
} else low = mid+1;
}
return low%MOD;
}
};TagsNth Magical Number Solution | LeetCode | Binary Searchleetcode
Raunit Verma
Technical Writer at CodingKaro
Share this on
