Math

50. Pow(x, n) Implement pow(x, n), which calculates x raised to the power n (i.e., xn). Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Constraints: -100.0 < x < 100.0 -231 <= n <= 231-1 -104 <= xn <= 104 Solution class Solution { public double myPow(double x, int n) { long N = n; if (n < 0) { x = 1.0 / x; N = -N; } long i = N; double res = 1.0; double current = x; while (i > 0) { if (i % 2 == 1) { res = res * current; } current = current * current; i = i / 2; } return res; } } Solution 2021-11-19 class Solution { public double myPow(double x, int n) { long N = n; if (n < 0) { x = 1 / x; N = -N; } double ans = 1.0; for (long i = N; i > 0; i = i / 2) { if (i % 2 == 1) { ans = ans * x; } x = x * x; } return ans; } } Solution 2021-01-30 class Solution { public double myPow(double x, int n) { long m = n; if (m == 0) return 1; if (m < 0) { m = -m; x = 1 / x; } double base = x; long degree = 1L; while (degree < m) { x = x * x; degree *= 2; } while (degree-- != m) { x /= base; } return x; } }

1071. Greatest Common Divisor of Strings For two strings s and t, we say “t divides s” if and only if s = t + … + t (t concatenated with itself 1 or more times) Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. Example 1: Input: str1 = "ABCABC", str2 = "ABC" Output: "ABC" Example 2: Input: str1 = "ABABAB", str2 = "ABAB" Output: "AB" Example 3: Input: str1 = "LEET", str2 = "CODE" Output: "" Example 4: Input: str1 = "ABCDEF", str2 = "ABC" Output: "" Constraints: ...

204. Count Primes Count the number of prime numbers less than a non-negative number, n. Example 1: Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Example 2: Input: n = 0 Output: 0 Example 3: Input: n = 1 Output: 0 Constraints: 0 <= n <= 5 * 106 Solution class Solution { public int countPrimes(int n) { boolean[] numbers = new boolean[n + 1]; for (int p = 2; p <= (int) Math.sqrt(n); p++) { if (numbers[p] == false) { for (int j = p + p; j < n; j += p) { numbers[j] = true; } } } int count = 0; for (int i = 2; i < n; i++) { if (numbers[i] == false) { count++; } } return count; } }