leetcode/problems/src/math/NthMagicalNumber.java at master · KindleBooks66/leetcode · GitHub

History

79 lines (74 loc) · 2.48 KB

Raw

package math;

import java.math.BigInteger;

/**

* Created by gouthamvidyapradhan on 23/03/2019 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

* Solution: O(log((2 ^ 64) - 1)) Lets take example of N = 5, A = 4 and B = 6 The multiple of A

* are 4, 8, 12, 16, 20, 24 . . . The multiple of B are 6, 12, 18, 24 . . .

* Lets take a arbitrary number E = 21 and see if this fits the correct answer E / A = 5 E / B =

* 3 This means there are 5 + 3 = 8 numbers which are divisible by either A or B such as 4, 6, 8,

* 12, 12, 16, 18, 20 but we have double counted number 12 so we have to reduce 8 by 1 therefore

* there are 7 numbers. But, 7 is greater than required number N = 5 that means we have to search

* between 0 and E - 1. Thus we can binary search to arrive at the answer.

* The number of common multiples such as 12 in the above example can be found by E / LCM(4, 6)

public class NthMagicalNumber {

/**

* Main method

* @param args

public static void main(String[] args) {

System.out.println(new NthMagicalNumber().nthMagicalNumber(3, 2, 4));

}

public int nthMagicalNumber(int N, int A, int B) {

final int CONST = 1000000007;

BigInteger bigInteger = new BigInteger(String.valueOf(A));

long aL = (long) A * B;

long lcm = aL / bigInteger.gcd(new BigInteger(String.valueOf(B))).longValue();

long l = 0, h = Long.MAX_VALUE;

while (l <= h) {

long m = l + (h - l) / 2;

int status = check(N, m, A, B, lcm);

if (status == 0) {

long modA = m % A;

long modB = m % B;

if (modA == 0 || modB == 0) return (int) (m % CONST);

else if (modA < modB) return (int) ((m - modA) % CONST);

else return (int) ((m - modB) % CONST);

} else if (status == -1) {

l = m + 1;

} else {

h = m - 1;

}

return 0;

}

private int check(int N, long num, int A, int B, long lcm) {

long sum = (num / A) + (num / B);

long common = num / lcm;

sum -= common;

if (sum == N) return 0;

else if (sum > N) return 1;

else return -1;

}

leetcode/problems/src/math/NthMagicalNumber.java at master · KindleBooks66/leetcode · GitHub

Uh oh!

Expand file tree

Breadcrumbs

NthMagicalNumber.java

Latest commit

History

Breadcrumbs

NthMagicalNumber.java

File metadata and controls