A positive integer is magical if it is divisible by either A or B.
Return the N-th magical number.  Since the answer may be very large, return it modulo 10^9 + 7.
 



Example 1:
Input: N = 1, A = 2, B = 3
Output: 2


Example 2:
Input: N = 4, A = 2, B = 3
Output: 6


Example 3:
Input: N = 5, A = 2, B = 4
Output: 10


Example 4:
Input: N = 3, A = 6, B = 4
Output: 8

 
Note:

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

Difficulty: interview

Starter code:

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        

Solutions:
class Solution:
    def NOD(self, a, b):
        if a == b:
            return a
        c = max(a,b)
        d = a + b - c
        c = c%d
        c = c if c>0 else d
        return self.NOD(c,d)
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        const = 10**9 + 7
        nod = self.NOD(A, B)
        nok = int(A*B/nod)
        C, D = min(A, B), max(A, B)
        k_C = nok//C
        k_D = nok//D
        k = k_C + k_D - 1
        div = N//k
        mod = N - div*k
        k_C_cur = (mod*k_C)//k
        k_D_cur = mod - k_C_cur
        #print(k_C, k_D, k, div, mod, k_C_cur, k_D_cur)
        while True:
            C_num = k_C_cur*C
            D_num = k_D_cur*D
            if -C < C_num - D_num < D:
                return (div*nok + max(C_num, D_num))%const
            elif C_num - D_num <= -C:
                k_D_cur -= 1
                k_C_cur += 1
            else:
                k_D_cur += 1
                k_C_cur -= 1

class Solution:
    def gcd(self, x, y):
        while y > 0:
            x, y = y, x % y
        return x

    def lcm(self, x, y):
        return x*y//self.gcd(x,y)
    
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        AB = self.lcm(A,B)

        def check(mid):
            ans = mid//A + mid//B - mid//(AB)
            return ans >= N
        
        lo, hi = 0, N*A
        while lo<hi:
            mid = (lo+hi)//2
            if check(mid):
                hi = mid
            else:
                lo = mid+1

        mod = 10**9+7
        return lo%mod

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        from fractions import gcd
        MOD = 10**9+7
        L = A/gcd(A,B)*B
        
        def max_unique_nums(x):
            return x//A+x//B-x//L
        
        lo = 0
        hi = N*min(A,B)
        while lo<hi:
            mid = (lo+hi)//2
            if max_unique_nums(mid)<N:
                lo =  mid + 1
            else:
                hi = mid
        return lo%MOD

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        from fractions import gcd
        MOD = 10**9 + 7

        L = A / gcd(A, B) * B
        M = L / A + L / B - 1
        q, r = divmod(N, M)

        if r == 0:
            return int(q * L) % MOD

        heads = [A, B]
        for _ in range(int(r) - 1):
            if heads[0] <= heads[1]:
                heads[0] += A
            else:
                heads[1] += B

        return int(q * L + min(heads)) % MOD

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        ## official solution
        def gcd(x, y):
            if y==0:
                return x
            return gcd(y, x%y)
            
        MOD = 10**9 + 7
        ## Least common multiple of A and B
        L = A // gcd(A, B) * B
        M = L//A + L//B - 1
        q, r = divmod(N, M)
        
        if r == 0:
            return q*L%MOD
        
        increments = [A, B]
        for _ in range(r-1):
            if increments[0]<=increments[1]:
                increments[0] += A
            else:
                increments[1] += B
        return (q*L+min(increments))%MOD


class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        # H.C.F of A and B
        x,y = min(A,B),max(A,B)
        print(x,y)
        hcf = x

        while (y%hcf !=0 or x%hcf!=0) and hcf>1:
            hcf -= 1
        print(hcf)
        gcd = int(x*y/hcf)
        print(gcd)
        start,end = x,N*x
        while start<=end:
            mid = start+int((end-start)/2)
            count = int(mid/x) + int(mid/y) - int(mid/gcd) 
            if count == N:
                break
            elif count >N:
                end = mid -1
            else:
                start = mid + 1
        while mid%x !=0 and mid%y !=0:
            mid -= 1
        return mid%(10**9 +7)

import math
class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        md = 10**9+7
        p = A*B//math.gcd(A,B)
        np = p//A+p//B-1
        n1 = N//np
        res = n1*(p%md)%md
        n2 = N%np
        i,j, curr = 0, 0, 0
        while i+j<n2:
            if A*(i+1) < B*(j+1):
                i += 1
                curr = A*i
            else:
                j += 1
                curr = B*j
        res = (res+curr)%md
        # print(i,j,n1,n2,np)
        return res



class Solution:
    modulo = 10**9+7
    def getMaxCommonFactor(self, A, B):
        while B > 0:
            A = A % B
            A, B = B, A
        return A
    
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        mcf = self.getMaxCommonFactor(A, B)
        period = (A * B // mcf) % self.modulo
        numinperiod = (A + B - mcf) // mcf
        base = N // numinperiod * period
        nums = [A*i for i in range(B//mcf)] + [B*i for i in range(1, A//mcf)]
        nums.sort()
        rem = nums[N % numinperiod]
        
        return (base + rem) % self.modulo
        


class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        
#         # O(N) solution -- TLE
#         i = 1 # multiplier of A
#         j = 1 # multiplier of B
        
#         res = 0
        
#         while N>0:
#             if A*i < B*j:
#                 res = A*i
#                 i += 1
#             elif A*i > B*j:
#                 res = B*j
#                 j += 1
#             else:
#                 res = A*i
#                 i += 1
#                 j += 1
#             N-=1
        
#         return res%(10**9+7)
    
        # O(logN) solution -- binary search
        def min_common_divisor(a, b):
            less = min(a, b)
            more = max(a, b)
            for i in range(1, less+1):
                if more*i % less == 0:
                    return more*i
            return a*b
        
        _cd = min_common_divisor(A, B)

        min_ = min(A, B)
        l, r = min_, min_*N+1
        while l<r:
            m = (l+r)>>1

            if m//A+m//B-m//_cd < N:
                l = m + 1
            elif m//A+m//B-m//_cd > N:
                r = m
            else:
                if m%A==0 and m%B==0:
                    return m % (10**9+7)
                else:
                    r = m

        return l % (10**9+7)

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        import math
        if (A % B == 0 or B % A == 0):
            return (N * min(A, B)) % (10**9 + 7)
        testRange = (1, N * min(A,B))
        testValue = int((testRange[1] + testRange[0]) / 2)
        magicNums = math.floor(testValue / A) + math.floor(testValue / B) - math.floor(testValue * math.gcd(A,B) / (A * B))
        while (magicNums != N):
            testRange = (testRange[0], testValue) if magicNums > N else (testValue, testRange[1])
            testValue = math.ceil((testRange[1] + testRange[0]) / 2)
            magicNums = math.floor(testValue / A) + math.floor(testValue / B) - math.floor(testValue * math.gcd(A,B) / (A * B))
        return max(int(testValue / A) * A, int(testValue / B) * B) % (10**9 + 7)

class Solution:
    def _lcm(self, a, b):
        return a * b // math.gcd(a, b)
    
    def _nth_magical_number_slow(self, n: int, a: int, b: int) -> int:
        if n == 0:
            return 0
        else:
            i, j = a, b
            count = 1
            while count < n:
                if i <= j:
                    i = i + a
                else:
                    j = j + b

                if i == j:
                    if a < b:
                        i = i + a
                    else:
                        j = j + b

                count += 1

            return min(i, j) % 1000000007
    
    def nthMagicalNumber(self, n: int, a_orig: int, b_orig: int) -> int:
        a, b = min(a_orig, b_orig), max(a_orig, b_orig)
        if a == b:
            return a * n % 1000000007
        else:
            lcm = self._lcm(a, b)
            k = lcm // a + lcm // b - 1
            return ((n // k) * lcm + self._nth_magical_number_slow(n % k, a, b)) % 1000000007


class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        a_t = A
        b_t = B
        col = []
        low_anc = a_t
        while a_t != b_t:
            if a_t < b_t:
                col.append(a_t)
                a_t = (a_t + A) #% (10 ** 9 + 7)
            else:
                col.append(b_t)
                b_t = (b_t + B) #% (10 ** 9 + 7)
        col.append(a_t)
        low_anc = a_t
        
        
        idx = (N - 1) % len(col)
        
        # 2,3,4,6
        
        ans = (N - 1) // len(col) * low_anc + col[idx]
        
        return ans % (10 ** 9 + 7)

def LCM(x, y):
    if x == y:
        return x
    bigger = max([x,y])
    smaller = min([x,y])
    res = bigger
    while res % smaller != 0:
        res += bigger
    return res

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        lcm = LCM(A,B)
        div = [0,lcm]
        for i in [A, B]:
            t = i
            while t < lcm:
                div.append(t)
                t += i
        
        div = sorted(div)
        cycle = len(div)-1
        
        return (div[N % cycle] + lcm * (N // cycle)) % 1000000007


class Solution:
    def _lcm(self, a, b):
        return a * b // math.gcd(a, b)
    
    def _nth_magical_number_slow(self, n: int, a: int, b: int) -> int:
        if n == 0:
            return 0
        else:
            i, j = a, b
            count = 1
            while count < n:
                if i <= j:
                    i = i + a
                else:
                    j = j + b

                if i == j:
                    if a < b:
                        i = i + a
                    else:
                        j = j + b

                count += 1

            return min(i, j)
    
    def nthMagicalNumber(self, n: int, a_orig: int, b_orig: int) -> int:
        a, b = min(a_orig, b_orig), max(a_orig, b_orig)
        if a == b:
            return a * n % 1000000007
        else:
            lcm = self._lcm(a, b)
            k = lcm // a + lcm // b - 1
            return ((n // k) * lcm + self._nth_magical_number_slow(n % k, a, b)) % 1000000007


import heapq
class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        def gcd(i, j):
            if i > j:
                i, j = j, i
            
            while i != 0:
                j %= i
                i, j = j, i
            return j
        
        common_mult = A * B // gcd(A, B)
        c_count = common_mult // A + common_mult // B - 1
        
        unit_count = N // c_count
        remainder = N % c_count
        
        base = (unit_count * common_mult) % (10**9 + 7)
        if remainder == 0:
            return base
        
        heap = [A, B]
        heapq.heapify(heap)
        while heap:
            curr = heapq.heappop(heap)
            remainder -= 1
            if remainder == 0:
                return (base + curr) % (10**9 + 7)
            
            if curr % A == 0:
                heapq.heappush(heap, curr + A)
            else:
                heapq.heappush(heap, curr + B)


def nww(a, b):
    bigger = max(a,b)
    smaller = min(a,b)
    result = bigger
    i = 2
    while(result % smaller != 0):
        result = bigger * i
        i += 1
    return result

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        nw = nww(A,B)
        la = list([A * x for x in range(1, nw//A)])
        lb = list([B * x for x in range(1, nw//B)])
        cycle = sorted([0]+la+lb)
        return (N // len(cycle) * nw + cycle[N % len(cycle)]) % (10**9+7)


class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        def gcd(a, b):
            while b:
                a, b = b, a%b
            return a
        
        LCM = A*B//gcd(A, B)
        m = LCM//A + LCM//B -1
        q, r = divmod(N, m)
        if r==0:
            return q*LCM%(10**9+7)
        # print(q, r, m, LCM)
        pa, pb = 0, 0
        for _ in range(r):
            nxt = min(A*(pa+1), B*(pb+1))
            if nxt==A*(pa+1):
                pa += 1
            if nxt==B*(pb+1):
                pb += 1
        
        return (q*LCM+nxt)%(10**9+7)
            
            
        
        


import fractions

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        self.normalize(A, B)
        multiples_before_lcm = self.get_multiples_before_lcm(A, B)
        mod = 10 ** 9 + 7
        div, rem = N // self.num_before_lcm, N % self.num_before_lcm
        return (div * self.lcm + multiples_before_lcm[rem]) % mod
        
    def normalize(self, A, B):
        self.gcd = fractions.gcd(A, B)
        self.lcm = A * B // self.gcd
        self.normA = A // self.gcd
        self.normB = B // self.gcd
        self.num_before_lcm = self.normA + self.normB - 1
    
    def get_multiples_before_lcm(self, A, B):
        nextAmult = A
        nextBmult = B
        multiples = self.num_before_lcm * [None]
        multiples[0] = 0
        i = 1
        while nextAmult < self.lcm and nextBmult < self.lcm:
            if nextAmult < nextBmult:
                multiples[i] = nextAmult
                nextAmult += A
            else:
                multiples[i] = nextBmult
                nextBmult += B
            i += 1
        while nextAmult < self.lcm:
            multiples[i] = nextAmult
            nextAmult += A
            i += 1
        while nextBmult < self.lcm:
            multiples[i] = nextBmult
            nextBmult += B
            i += 1
        assert i == self.num_before_lcm
        return multiples

from fractions import gcd
class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        l = 0
        r = N*(min(A, B))
        
        lcm = (A*B)//gcd(A, B)
        
        def checkNum(x):
            ans = x//A + x//B - x//lcm
            return ans >= N
        
        if N == 1:
            return min(A, B)
        while r > l:
            m = (r + l) // 2
            if checkNum(m):
                r = m
            else:
                l = m + 1
        return l%(10**9+7)

class Solution:
    
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        
        if A > B:
            A, B = B, A
            
        if B % A == 0:
            return A * N % 1000000007
        
        for i in range(1,A+1):
            if B*i % A == 0:
                break
        
        LCM = B*i
        
        nAB = LCM // A + i - 1
        
        r = N // nAB
        
        N %= nAB
        
#         print(nAB,r,N)
        
        return (r * LCM + sorted(set([A*i for i in range(N+1)]) | set([B*i for i in range(N+1)]))[N]) % 1000000007
        


class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        def lcm(a, b):
            return a * b // gcd(a, b)
        val = lcm(A, B)
        magicals = set()
        for i in range(1, val//A + 1):
            magicals.add(i * A)
        for i in range(1, val//B + 1):
            magicals.add(i * B)
        sorted_magicals = sorted(magicals)
        return (sorted_magicals[(N-1) % len(sorted_magicals)] + ((N - 1) // len(sorted_magicals) * sorted_magicals[-1])) % (10**9 + 7)

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        def compute_gcd(x, y):
            if y == 0: return x
            return compute_gcd(y, x%y)

        # This function computes LCM
        def compute_lcm(x, y):
            lcm = (x*y)//compute_gcd(x,y)
            return lcm


        C = compute_lcm(A,B)
        l = min(A,B)
        h = N*max(A,B)
        #print(C)
        while (l < h):
            mid = (l+h)//2
            m = mid//A + mid//B - mid//C
            if m>=N:
                h = mid
            else:
                l = mid + 1
        return l %(10**9+7)
      
            


class Solution(object):
    def nthMagicalNumber(self, N, A, B):
        from fractions import gcd
        MOD = 10**9 + 7
        L = A // gcd(A,B) * B

        def magic_below_x(x):
            # How many magical numbers are <= x?
            return x // A + x // B - x // L

        lo = 0
        hi = N * min(A, B)
        while lo < hi:
            mi = (lo + hi) // 2
            if magic_below_x(mi) < N:
                lo = mi + 1
            else:
                hi = mi

        return lo % MOD

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        d = gcd(A, B)
        A //= d
        B //= d

        def how_many_below(n):
            return n//A+n//B-n//(A*B)

        lo = N-1
        hi = min(A, B)*N

        while hi - lo > 1:
            h = (hi+lo)//2
            if how_many_below(h) >= N:
                hi = h
            else:
                lo = h
        return hi*d % (10**9+7)


def gcd(a, b):
    while a:
        a, b = b % a, a
    return b


class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        
        lcm = A * B // math.gcd(A,B)
        
        cnt = lcm // A + lcm // B - 1
        
        i = N // cnt
        j = N % cnt
        
        
        def count(x, lcm):
            
            return x//A + x//B - x//lcm
        
        l, r = 0, A*B
        
        while l < r:
            mid = l + (r-l)//2
            
            c = count(mid, lcm)
            
            if c < j:
                l = mid + 1
            else:
                r = mid
        
        return (i * lcm + l) % (10**9+7)

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        def lcm(a, b):
            return a * b // gcd(a, b)
        val = lcm(A, B)
        def number_magic_below(x):
            return x // A + x // B - x // val
        
        lo = min(A, B)
        hi = N * min(A, B)
        while lo < hi:
            mid = (lo + hi) // 2
            if number_magic_below(mid) < N:
                lo = mid + 1
            else:
                hi = mid
        return lo % (10**9 + 7)