ðŸ¥‡

# Nth Magical Number

Created
2021/12/11 02:12
ë¬¸ì œ ë²ˆí˜¸
878
ì¹´í…Œê³ ë¦¬
Math
Binary Search

### Code

 .css-15tnwsa{max-width:100%;width:100%;white-space:pre-wrap;word-break:break-word;padding:7px 9px;background-color:transparent;font-size:14px;line-height:20px;min-height:1em;}.css-15tnwsa:empty::after{content:" ";}ì œì¶œ ë‚ ì§œ ì‹œê°„ ë©”ëª¨ë¦¬ 2021/12/11 0 ms 2 MB
// 878. Nth Magical Number // // https://leetcode.com/problems/nth-magical-number/ const mod = 1e9 + 7 // gcd function finds the Greatest Common Divisor. func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) } // lcm function finds the Least Common Multiple. func lcm(a, b int) int { return (a * b) / gcd(a, b) } // nthMagicalNumber function finds the number which is fit to the argument n. // n is quite big (1 <= n <= 10^9). // To get the rank of the number, O(N) or O(logN) would be appropriate. // Searching numbers are ascending orders, so Binary Search is a good strategy. // if n = 4, a = 2, b = 3, answer is 6. // -> ( rank of a + rank of b ) - ( common number rank ) = n th number // -> ( answer / a + answer / b) - ( lcm rank) = n th number func nthMagicalNumber(n int, a int, b int) int { var div int = lcm(a, b) var low, high int = 0, int(^uint(0) >> 1) for low < high { mid := (low + high) / 2 if mid/a+mid/b-mid/div < n { low = mid + 1 } else { high = mid } } return low % mod }
Go
ë³µì‚¬