1) for negative num : transform to positive int first, do 10 based -> 7 based op
                      then add "-" at beginning
2) for positive num : do 10 based -> 7 based op
                    -> keep checking if num % N == 0
                    -> if not == 0, keep do  num = num % N, and append cur result to res
                    -> reverse res
                    -> make array to string
                    -> return result
3) example:
    100 (10 based) -> "202" (7 based)

    tmp = 100
    a, b = divmod(tmp, 7)  -> a = 14, b = 2,  tmp  = 14
    a, b = divmod(tmp, 7)  -> a= 2, b = 0, tmp = 2
    a, b = divmod(tmp, 7)  -> a = 0, b = 2

    -> so res = [2,0,2]

#### 1-1-0') 把 `N based integer to 10 based`
```python
# V1
# LC 1022. Sum of Root To Leaf Binary Numbers
def convertToBaseN(num, n):
    return int(str(num), n)

In [34]: int("100",7)
Out[34]: 49

In [35]: int("14",7)
Out[35]: 11

In [36]: int("66",7)
Out[36]: 48

# LC 762 Prime Number of Set Bits in Binary Representation
def check_prime(x):
    if x <= 1:
        return False
    for i in range(2, int(x**(0.5)+1)):
        if x % i == 0:
            return False
    return True

# LC 204 Count Primes
# V0
# IDEA : set
# https://leetcode.com/problems/count-primes/discuss/1343795/python%3A-sieve-of-eretosthenes
# prime(x) : number of prime in [0, x]
# prime(0) = 0
# prime(1) = 0
# prime(2) = 0
# prime(3) = 1
# prime(4) = 2
# prime(5) = 3
class Solution:
    def countPrimes(self, n):
        # using sieve of eretosthenes algorithm
        if n < 2: return 0
        nonprimes = set()
        for i in range(2, round(n**(1/2))+1):
            if i not in nonprimes:
                for j in range(i*i, n, i):
                    nonprimes.add(j)
        return n - len(nonprimes) - 2  # remove prime(1), prime(2)

// java
// algorithm book (labu) p.362
// V1
int countPrimes(int n){
    boolean[] isPrime = new boolean[n];

    // init array to true
    Arrays.fill(isPrime, true);

    // prime number start from 2
    for (int i = 2; i < n; i++){
        if (isPrime[i]){
            // if i is prime, then i's multiple is NOT prime
            for (int j = 2 * i; j < n; j += i){
                isPrime[j] = false;
            }
        }
    }

    int count = 0;
    for (int i = 2; i < n; i++){
        if (isPrime[i]){
            count ++;
        }
    }
    return count;
}

// java
// algorithm book (labu) p.363
// V1' (optimization)
int countPrimes(int n){
    boolean[] isPrime = new boolean[n];

    // init array to true
    Arrays.fill(isPrime, true);

    // prime number start from 2
    for (int i = 2; i * i  < n; i++){
        if (isPrime[i]){
            // if i is prime, then i's multiple is NOT prime
            /** optimize here :  make j start from i * i, instead of 2 * i */
            // (the only difference between V1 and V1')
            for (int j = i * i; j < n; j += i){
                isPrime[j] = false;
            }
        }
    }

    int count = 0;
    for (int i = 2; i < n; i++){
        if (isPrime[i]){
            count ++;
        }
    }
    return count;
}

Divisors come in PAIRS that multiply to x:   d  ×  (x / d) = x
  12 = 1×12 = 2×6 = 3×4
       ^         ^
       d <= √12  the partner is >= √12

So one member of every pair is <= √x  ->  scanning d = 1..√x sees them all.

# python
# GENERAL PATTERN: all divisors of x, ascending
# IDEA: each divisor d <= sqrt(x) hands you its partner x // d for free
# time = O(sqrt(x)), space = O(number of divisors)
def get_divisors(x):
    small, large = [], []
    d = 1
    while d * d <= x:
        if x % d == 0:
            small.append(d)
            if d != x // d:          # perfect square: don't add sqrt(x) twice
                large.append(x // d)
        d += 1
    return small + large[::-1]        # large is descending -> reverse to merge sorted

# get_divisors(12) -> [1, 2, 3, 4, 6, 12]
# get_divisors(36) -> [1, 2, 3, 4, 6, 9, 12, 18, 36]   (6 counted once)

// java
// GENERAL PATTERN: all divisors of x, ascending
// time = O(sqrt(x)), space = O(number of divisors)
public List<Integer> getDivisors(int x) {
    List<Integer> small = new ArrayList<>(), large = new ArrayList<>();
    for (int d = 1; (long) d * d <= x; d++) {
        if (x % d == 0) {
            small.add(d);
            if (d != x / d) large.add(x / d);   // skip the duplicate sqrt
        }
    }
    Collections.reverse(large);
    small.addAll(large);
    return small;
}

# python
# GENERAL PATTERN: distinct prime factors of x  (x >= 1)
# IDEA: TRIAL DIVISION — strip each factor out completely, so every hit is prime
# time = O(sqrt(x)), space = O(number of distinct primes)
def get_prime_factors(x):
    """Returns the set of distinct prime factors of x."""
    factors = set()
    d = 2
    while d * d <= x:
        if x % d == 0:
            factors.add(d)
            while x % d == 0:     # strip ALL copies of d
                x //= d
        d += 1                    # x has shrunk, so the loop bound shrinks with it
    if x > 1:                     # leftover > 1 is a prime bigger than sqrt(original x)
        factors.add(x)
    return factors

// java
// GENERAL PATTERN: distinct prime factors of x
// time = O(sqrt(x)), space = O(number of distinct primes)
public List<Integer> getPrimeFactors(int x) {
    List<Integer> factors = new ArrayList<>();
    for (int d = 2; (long) d * d <= x; d++) {
        if (x % d == 0) {
            factors.add(d);
            while (x % d == 0) x /= d;   // strip ALL copies of d
        }
    }
    if (x > 1) factors.add(x);           // the last prime, > sqrt
    return factors;
}

d=2 : 360 % 2 == 0  -> add 2, strip: 360 -> 180 -> 90 -> 45
d=3 :  45 % 3 == 0  -> add 3, strip:  45 ->  15 -> 5
d=4 : 4*4 = 16 > 5  -> loop ends       (bound checks the SHRUNK x, not the original)
x=5 > 1             -> add 5
=> {2, 3, 5}         (360 = 2³ × 3² × 5)

# python
# GENERAL PATTERN: SPF sieve -> factor any x <= MAXV in O(log x)
# time = O(MAXV log log MAXV) build, O(log x) per query; space = O(MAXV)
MAXV = 100_001
spf = list(range(MAXV))                     # spf[i] = smallest prime factor of i
for i in range(2, int(MAXV ** 0.5) + 1):
    if spf[i] == i:                         # i is prime
        for j in range(i * i, MAXV, i):
            if spf[j] == j:                 # only the FIRST prime to reach j wins
                spf[j] = i

def prime_factors_fast(x):
    out = set()
    while x > 1:
        p = spf[x]
        out.add(p)
        while x % p == 0:
            x //= p
    return out

// java
// GENERAL PATTERN: SPF sieve
// time = O(MAXV log log MAXV) build, O(log x) per query; space = O(MAXV)
static final int MAXV = 100_001;
static int[] spf = new int[MAXV];
static {
    for (int i = 0; i < MAXV; i++) spf[i] = i;
    for (int i = 2; (long) i * i < MAXV; i++)
        if (spf[i] == i)
            for (int j = i * i; j < MAXV; j += i)
                if (spf[j] == j) spf[j] = i;
}

public List<Integer> primeFactorsFast(int x) {
    List<Integer> out = new ArrayList<>();
    while (x > 1) {
        int p = spf[x];
        out.add(p);
        while (x % p == 0) x /= p;
    }
    return out;
}

# python
# LC 4032. Longest Subarray With at Most K Distinct Prime Factors
# IDEA: SLIDING WINDOW over a {prime: count} map; union size == len(map)
# time = O(n * sqrt(A)) to factor + O(n * distinct) window, space = O(n * distinct)
from collections import defaultdict

def longestSubarray(nums, k):
    facs = [get_prime_factors(v) for v in nums]   # factor each element ONCE
    cnt = defaultdict(int)
    left = best = 0
    for right in range(len(nums)):
        for p in facs[right]:
            cnt[p] += 1
        while len(cnt) > k:                       # too many distinct primes -> shrink
            for p in facs[left]:
                cnt[p] -= 1
                if cnt[p] == 0:
                    del cnt[p]                    # MUST delete, len(cnt) is the answer
            left += 1
        best = max(best, right - left + 1)
    return best

# nums = [7,6,10,12,11], k = 3 -> 3   ([6,10,12] -> {2,3,5})
# nums = [4,6,9,18],     k = 4 -> 4   (whole array -> {2,3})
# nums = [6,10,15],      k = 2 -> 1   (any pair already needs {2,3,5})

// java
// LC 4032. Longest Subarray With at Most K Distinct Prime Factors
// time = O(n * sqrt(A)), space = O(n * distinct)
public int longestSubarray(int[] nums, int k) {
    int n = nums.length;
    List<List<Integer>> facs = new ArrayList<>();
    for (int v : nums) facs.add(getPrimeFactors(v));

    Map<Integer, Integer> cnt = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < n; right++) {
        for (int p : facs.get(right)) cnt.merge(p, 1, Integer::sum);
        while (cnt.size() > k) {
            for (int p : facs.get(left)) {
                if (cnt.merge(p, -1, Integer::sum) == 0) cnt.remove(p);
            }
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

(a * 10 + 1) % k  ==  ((a % k) * 10 + 1) % k

int remainder = 0;
for (int len = 1; len <= k; len++) {
    remainder = (remainder * 10 + 1) % k;  // build next repunit mod k
    if (remainder == 0) return len;         // found divisible repunit
}
return -1;

if (k % 2 == 0 || k % 5 == 0) return -1;

// LC 1015 full solution
public int smallestRepunitDivByK(int k) {
    if (k % 2 == 0 || k % 5 == 0) return -1;
    int remainder = 0;
    for (int len = 1; len <= k; len++) {
        remainder = (remainder * 10 + 1) % k;
        if (remainder == 0) return len;
    }
    return -1;
}

A ----- B
|       |
|       |
D ----- C

AB = side
BC = side
CD = side
DA = side
AC = diagonal
BD = diagonal

# LC 593. Valid Square
class Solution(object):
    def validSquare(self, p1, p2, p3, p4):
        points = [p1, p2, p3, p4]
        dists = []

        for i in range(4):
            for j in range(i + 1, 4):
                dists.append(self.get_len(
                    points[i][0], points[i][1],
                    points[j][0], points[j][1]
                ))

        dists.sort()

        return (
            dists[0] > 0 and                 # no overlapping points
            dists[0] == dists[1] ==
            dists[2] == dists[3] and         # four equal sides
            dists[4] == dists[5] and         # two equal diagonals
            dists[4] > dists[0]              # diagonal longer than side
        )

    def get_len(self, x1, y1, x2, y2):
        # use squared distance -> avoid float/sqrt precision issues
        return (x1 - x2) ** 2 + (y1 - y2) ** 2

class Solution(object):
    def validSquare(self, p1, p2, p3, p4):
        def dist(a, b):
            return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

        points = [p1, p2, p3, p4]
        lookup = set(
            dist(points[i], points[j])
            for i in range(4) for j in range(i + 1, 4)
        )
        return 0 not in lookup and len(lookup) == 2

F(0) = 0*A + 1*B + 2*C + 3*D
F(1) = 0*D + 1*A + 2*B + 3*C
F(2) = 0*C + 1*D + 2*A + 3*B
F(3) = 0*B + 1*C + 2*D + 3*A

sum = A + B + C + D                 # total sum, weight-independent

F(1) = F(0) + sum - 4*D             # D's weight: 3 -> 0, i.e. -4*D; everything else: +1 each -> +sum
F(2) = F(1) + sum - 4*C
F(3) = F(2) + sum - 4*B

F(k) = F(k-1) + sum(nums) - n * nums[n-k]

# LC 396. Rotate Function
# time = O(n), space = O(1)
class Solution(object):
    def maxRotateFunction(self, nums):
        size = len(nums)
        total = sum(nums)
        f = sum(i * x for i, x in enumerate(nums))  # F(0)

        ans = f
        for i in range(size - 1, 0, -1):
            # nums[i] is the element wrapping to front: weight n-1 -> 0
            f += total - size * nums[i]
            ans = max(ans, f)
        return ans

n = 6, s = 3, m = 5

              s+2m-1=12          s+3m-2=16
                 /\                 /\
      s+m=8    /    \             /
        /\    /      \           /
       /   \ /   s+2m-2=11      /
      /   s+m-1=7              /
   s=3

seq = [3, 8, 7, 12, 11, 16]
       ^  +5 -1  +5  -1  +5

max = s + k*m - (k - 1)
    = s + k*(m - 1) + 1        , where k = n // 2

# python
# LC 3993. Maximum Value of an Alternating Sequence
# time = O(1), space = O(1)
class Solution(object):
    def maximumValue(self, n, s, m):
        # IDEA: GREEDY ZIGZAG -> CLOSED FORM
        # go up by m, come down by only 1 (strict inequality), repeat

        # edge case: length-1 sequence is just [s]
        if n == 1:
            return s

        k = n // 2                 # number of "up" moves == number of peaks
        return s + k * (m - 1) + 1  # == s + k*m - (k-1)

// java
// LC 3993 - Maximum Value of an Alternating Sequence
// time = O(1), space = O(1)
public long maximumValue(int n, int s, int m) {
    // IDEA: GREEDY ZIGZAG -> CLOSED FORM
    if (n == 1) {
        return s;
    }
    long k = n / 2;                    // peaks == up moves
    return s + k * (m - 1) + 1;        // use long: n, s up to 1e9
}

Proof sketch — suppose two parts differ by >= 2, i.e.  a >= b + 2
Replace (a, b) with (a-1, b+1)  -> sum is unchanged

  (a-1)(b+1) = ab + a - b - 1
             >= ab + 1          , since a - b >= 2

  -> product STRICTLY increases
  -> keep rebalancing until every pair differs by <= 1

q, r = divmod(n, k)          # q = n // k  (商數), r = n % k  (餘數)

  ->  r     parts have value (q + 1)      <-- the "leftover" r units are spread
  ->  (k-r) parts have value  q               one-by-one over r parts

Sanity check the sum:
  r*(q+1) + (k-r)*q  =  r*q + r + k*q - r*q  =  k*q + r  =  n   ✅

Max product for that k:
  P(n, k) = (q + 1)^r  *  q^(k - r)

n = 10, k = 3
  q, r = divmod(10, 3) = (3, 1)
  -> 1 part  of q+1 = 4
  -> 2 parts of q   = 3
  -> [4, 3, 3]   sum = 10 ✅   product = 4*3*3 = 36

Compare with UNEVEN splits of the same n and k:
  [8, 1, 1] -> 8      [6, 2, 2] -> 24     [5, 4, 1] -> 20
  [4, 3, 3] -> 36  <-- max, and it is the "even" one ✅

# python
# GENERAL PATTERN: split n into k parts as evenly as possible
def get_product(n, k):
    """
    Split n into k parts as evenly as possible,
    return their (maximum) product.
    """
    ### NOTE !!! get q (商數), r (餘數) via divmod
    q = n // k
    r = n % k

    ### NOTE !!!
    #   r      parts have value q + 1   (the remainder is spread 1 unit each)
    #   k - r  parts have value q
    product = 1

    ### NOTE !!! build the product from q, r
    for _ in range(r):
        product *= (q + 1)

    for _ in range(k - r):
        product *= q

    return product


# one-liner form (same thing, via pow)
def get_product(n, k):
    q, r = divmod(n, k)
    return (q + 1) ** r * q ** (k - r)


# the parts themselves (when you need the list, not the product)
def split_evenly(n, k):
    q, r = divmod(n, k)
    return [q + 1] * r + [q] * (k - r)

// java
// GENERAL PATTERN: split n into k parts as evenly as possible
long getProduct(int n, int k) {
    int q = n / k;          // 商數
    int r = n % k;          // 餘數

    long product = 1;
    for (int i = 0; i < r; i++)     product *= (q + 1);   // r parts of q+1
    for (int i = 0; i < k - r; i++) product *= q;         // k-r parts of q
    return product;
}

# python
# LC 343. Integer Break
# IDEA: MATH — for each k, split evenly (divmod); take max over all k
# time = O(n^2), space = O(1)
class Solution(object):
    def integerBreak(self, n):
        # edge case: k >= 2 is FORCED, so 2 must become 1 + 1
        if n == 2:
            return 1

        max_product = 1

        # try every possible number of parts
        for k in range(2, n + 1):
            max_product = max(max_product, self.get_product(n, k))

        return max_product

    def get_product(self, n, k):
        q, r = n // k, n % k
        # r parts of (q+1),  k-r parts of q
        product = 1
        for _ in range(r):
            product *= (q + 1)
        for _ in range(k - r):
            product *= q
        return product

Splitting n into parts of size x gives n/x parts -> product = x^(n/x)
Maximize  f(x) = x^(1/x)   ->   maximum at x = e ≈ 2.718

Integer candidates around e:
  2^(1/2) ≈ 1.414
  3^(1/3) ≈ 1.442   <-- WINNER
  4^(1/4) ≈ 1.414   (== 2, since 4 = 2+2 -> 2*2 = 4)

Also, by direct comparison:
  x >= 5  ->  3 * (x - 3) > x     -> ALWAYS split a part of size >= 5
  x == 4  ->  2 * 2 == 4          -> splitting 4 is neutral
  part == 1 is pure waste (multiplying by 1 does nothing)

=> every part in the optimum is a 3 or a 2, and we prefer 3s.

n % 3 == 0  ->  3^(n/3)                    e.g. 9  = 3+3+3      -> 27
n % 3 == 2  ->  3^(n/3) * 2                e.g. 11 = 3+3+3+2    -> 54
n % 3 == 1  ->  3^(n/3 - 1) * 4            e.g. 10 = 3+3+4      -> 36
                ^^^^^^^^^^^^^^^ borrow one 3 back and use 2+2,
                because 3*1 = 3  <  2*2 = 4

# python
# LC 343 - O(log n) math solution
# time = O(log n) (pow), space = O(1)
class Solution(object):
    def integerBreak(self, n):
        # n = 2 -> 1,  n = 3 -> 2  (forced to split, so we lose)
        if n < 4:
            return n - 1

        if n % 3 == 0:
            return 3 ** (n // 3)
        elif n % 3 == 2:
            return 3 ** (n // 3) * 2
        else:                      # n % 3 == 1 -> use 2*2 instead of 3*1
            return 3 ** (n // 3 - 1) * 4

# python
# LC 343 - O(n) DP solution (safest if you can't recall the math)
# dp[x] = max product of breaking x  (x itself allowed as a "part" for x >= 4)
# time = O(n), space = O(n)
class Solution(object):
    def integerBreak(self, n):
        if n <= 3:
            return n - 1
        dp = [0] * (n + 1)
        dp[2], dp[3] = 2, 3        # NOTE: 3 (not 2), because 3 can stay whole here
        for x in range(4, n + 1):
            dp[x] = max(3 * dp[x - 3], 2 * dp[x - 2])
        return dp[n]

x^n  =  (x^2)^(n/2)              , n even
     =  x * (x^2)^((n-1)/2)      , n odd

-> equivalently: n = sum of powers of 2 (its binary bits)
   x^13 = x^(1101b) = x^8 * x^4 * x^1

x = 2, n = 13 (1101b)

step | bit | x (running square) | res
-----|-----|--------------------|------------
  0  |  1  | 2                  | 1 * 2   = 2       <- x^1
  1  |  0  | 4                  | 2                 (skip)
  2  |  1  | 16                 | 2 * 16  = 32      <- x^1 * x^4
  3  |  1  | 256                | 32 * 256 = 8192   <- x^1 * x^4 * x^8

2^13 = 8192  ✅

// java
// LC 50 - Pow(x, n)
// IDEA: FAST POWER (BINARY EXPONENTIATION) - square the base, halve the exponent
// time = O(log n), space = O(1)
public double myPow(double x, int n) {
    /** NOTE !!! promote to long FIRST
     *  -n overflows when n == Integer.MIN_VALUE (-2^31 has no positive int)
     */
    long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }

    double res = 1.0;
    while (N > 0) {
        // if current bit is 1 -> accumulate the current square
        if ((N & 1) == 1) {
            res *= x;
        }
        x *= x;      // x -> x^2 -> x^4 -> x^8 ...
        N >>= 1;
    }
    return res;
}

# python
# LC 50. Pow(x, n)
# IDEA: FAST POWER (BINARY EXPONENTIATION)
# time = O(log n), space = O(1)
class Solution(object):
    def myPow(self, x, n):
        # negative exponent -> invert the base
        if n < 0:
            x, n = 1 / x, -n

        res = 1.0
        while n:
            ### NOTE !!! if current bit is 1, accumulate the current square
            if n & 1:
                res *= x
            x *= x        # x -> x^2 -> x^4 -> x^8 ...
            n >>= 1
        return res

// java
// GENERAL PATTERN: (base ^ exp) % mod
// DOMAIN: exp >= 0, mod > 0, mod < ~3e9 (so `res * base` fits in a long).
//         Negative base -> use Math.floorMod(base, mod); negative exp needs a modular inverse.
// time = O(log exp), space = O(1)
long powMod(long base, long exp, long mod) {
    long res = 1 % mod;      // NOTE: `1 % mod`, not `1` -> handles mod == 1
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            res = res * base % mod;   // use long, `int * int` overflows
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

# python
# GENERAL PATTERN: (base ** exp) % mod
# DOMAIN: exp >= 0, mod > 0. A negative `exp` never terminates here
#         (`exp >>= 1` on a negative int floors to -1 forever) -> use a modular inverse instead.
# time = O(log exp), space = O(1)
def pow_mod(base, exp, mod):
    res = 1 % mod
    base %= mod
    while exp:
        if exp & 1:
            res = res * base % mod
        base = base * base % mod
        exp >>= 1
    return res

# python builtin does exactly this:
#   pow(base, exp, mod)

gcd(48, 18)
  -> gcd(18, 48 % 18 = 12)
  -> gcd(12, 18 % 12 = 6)
  -> gcd(6,  12 % 6  = 0)
  -> 6

lcm(a, b) = a * b / gcd(a, b)
          = a / gcd(a, b) * b        <-- divide FIRST to avoid overflow

// java
// GENERAL PATTERN: Euclid gcd / lcm
// time = O(log(min(a,b))), space = O(1)
int gcd(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;          // NOTE: gcd(x, 0) == x, gcd(0, 0) == 0
}                      // (caveat: Math.abs(Integer.MIN_VALUE) stays negative -> use long if that's reachable)

long lcm(int a, int b) {
    // NOTE !!! lcm with 0 is 0 -> guard first, else gcd(0, 0) == 0 divides by zero
    if (a == 0 || b == 0) {
        return 0;
    }
    // NOTE !!! divide BEFORE multiplying, else a*b can overflow
    return (long) Math.abs(a) / gcd(a, b) * Math.abs(b);
}

# python
# GENERAL PATTERN: Euclid gcd / lcm
# time = O(log(min(a,b))), space = O(1)
def my_gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

def my_lcm(a, b):
    ### NOTE !!! lcm with 0 is 0 -> guard first, else my_gcd(0, 0) == 0 divides by zero
    if a == 0 or b == 0:
        return 0
    return abs(a) // my_gcd(a, b) * abs(b)

# python builtin:
#   from math import gcd, lcm      # lcm needs python 3.9+

// java
// LC 149 - Max Points on a Line
// IDEA: GCD-REDUCED SLOPE AS HASH KEY (no float division)
// time = O(n^2), space = O(n)
public int maxPoints(int[][] points) {
    int n = points.length;
    if (n <= 2) {
        return n;
    }

    int best = 1;
    for (int i = 0; i < n; i++) {
        // slope -> how many points share it with points[i]
        Map<String, Integer> cnt = new HashMap<>();
        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];

            /** NOTE !!! reduce by gcd -> canonical direction vector */
            int g = gcd(dx, dy);
            if (g != 0) {
                dx /= g;
                dy /= g;
            }

            /** NOTE !!! normalize sign, so (1,2) and (-1,-2) are the SAME line */
            if (dx < 0 || (dx == 0 && dy < 0)) {
                dx = -dx;
                dy = -dy;
            }

            int c = cnt.merge(dx + "/" + dy, 1, Integer::sum);
            best = Math.max(best, c + 1);   // +1 -> include points[i] itself
        }
    }
    return best;
}

# python
# LC 149. Max Points on a Line
# IDEA: GCD-REDUCED SLOPE AS HASH KEY (no float division)
# time = O(n^2), space = O(n)
from math import gcd

class Solution(object):
    def maxPoints(self, points):
        n = len(points)
        if n <= 2:
            return n

        best = 1
        for i in range(n):
            cnt = {}
            x1, y1 = points[i]
            for j in range(i + 1, n):
                dx = points[j][0] - x1
                dy = points[j][1] - y1

                ### NOTE !!! reduce by gcd -> canonical direction
                g = gcd(abs(dx), abs(dy))
                if g:
                    dx //= g
                    dy //= g

                ### NOTE !!! normalize sign
                if dx < 0 or (dx == 0 and dy < 0):
                    dx, dy = -dx, -dy

                cnt[(dx, dy)] = cnt.get((dx, dy), 0) + 1
                best = max(best, cnt[(dx, dy)] + 1)   # +1 -> points[i] itself
        return best

// java
// LC 365 - Water and Jug Problem
// IDEA: BEZOUT -> reachable amounts == multiples of gcd(x, y)
// time = O(log(min(x,y))), space = O(1)
public boolean canMeasureWater(int x, int y, int target) {
    if (target == 0) {
        return true;                       // NOTE: guard first, gcd(0,0) == 0
    }
    if ((long) x + y < target) {
        return false;                      // can't hold more than both jugs
    }
    return target % gcd(x, y) == 0;
}

# python
# LC 365. Water and Jug Problem
# IDEA: BEZOUT -> reachable amounts == multiples of gcd(x, y)
# time = O(log(min(x,y))), space = O(1)
from math import gcd

class Solution(object):
    def canMeasureWater(self, x, y, target):
        if target == 0:
            return True                    # guard first (gcd(0,0) == 0)
        if x + y < target:
            return False
        return target % gcd(x, y) == 0

// java
// LC 69 - Sqrt(x)
// IDEA: BINARY SEARCH ON ANSWER, keep last feasible mid
// time = O(log x), space = O(1)
public int mySqrt(int x) {
    if (x < 2) {
        return x;                    // 0 -> 0, 1 -> 1
    }
    int lo = 1, hi = x / 2, ans = 1; // NOTE: for x >= 2, isqrt(x) <= x/2
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        /** NOTE !!! cast to long -> mid * mid overflows int */
        long sq = (long) mid * mid;
        if (sq == x) {
            return mid;
        } else if (sq < x) {
            ans = mid;               // feasible -> remember, then push right
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

# python
# LC 69. Sqrt(x)
# IDEA: BINARY SEARCH ON ANSWER, keep last feasible mid
# time = O(log x), space = O(1)
class Solution(object):
    def mySqrt(self, x):
        if x < 2:
            return x
        lo, hi, ans = 1, x // 2, 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            sq = mid * mid
            if sq == x:
                return mid
            elif sq < x:
                ans = mid            # feasible -> remember it
                lo = mid + 1
            else:
                hi = mid - 1
        return ans

r_next = (r + x / r) / 2      # integer division is fine, it converges DOWN to isqrt(x)
loop while r * r > x

// java
// LC 69 - Sqrt(x)  (Newton)
// time = O(log x), space = O(1)
public int mySqrtNewton(int x) {
    long r = x;                     // NOTE: long, r*r overflows int
    while (r * r > x) {
        r = (r + x / r) / 2;
    }
    return (int) r;                 // x == 0 -> loop never runs -> 0
}

# python
# LC 69. Sqrt(x)  (Newton)
# time = O(log x), space = O(1)
class Solution(object):
    def mySqrt(self, x):
        r = x
        while r * r > x:
            r = (r + x // r) // 2
        return r

// java
// LC 367 - Valid Perfect Square
// time = O(log num), space = O(1)
public boolean isPerfectSquare(int num) {
    long r = num;
    while (r * r > num) {
        r = (r + num / r) / 2;
    }
    return r * r == num;            // only difference vs LC 69
}

# python
# LC 367. Valid Perfect Square
# time = O(log num), space = O(1)
class Solution(object):
    def isPerfectSquare(self, num):
        r = num
        while r * r > num:
            r = (r + num // r) // 2
        return r * r == num

# python
# LC 633. Sum of Square Numbers
# IDEA: TWO POINTERS on [0, isqrt(c)]
# time = O(sqrt(c)), space = O(1)
from math import isqrt

class Solution(object):
    def judgeSquareSum(self, c):
        a, b = 0, isqrt(c)
        while a <= b:
            cur = a * a + b * b
            if cur == c:
                return True
            elif cur < c:
                a += 1               # need bigger -> raise the low end
            else:
                b -= 1               # too big -> lower the high end
        return False

// java
// LC 633 - Sum of Square Numbers
// time = O(sqrt(c)), space = O(1)
public boolean judgeSquareSum(int c) {
    long a = 0, b = (long) Math.sqrt(c);
    while (a <= b) {
        long cur = a * a + b * b;
        if (cur == c) {
            return true;
        } else if (cur < c) {
            a++;
        } else {
            b--;
        }
    }
    return false;
}

// java
// LC 384 - Shuffle an Array
// IDEA: FISHER-YATES (swap a[i] with a random j in [0, i])
// time = O(n) per shuffle, space = O(n)
class Solution {
    private final int[] original;
    private final Random rand = new Random();

    public Solution(int[] nums) {
        this.original = nums.clone();
    }

    public int[] reset() {
        return original.clone();
    }

    public int[] shuffle() {
        int[] a = original.clone();
        for (int i = a.length - 1; i > 0; i--) {
            /** NOTE !!! nextInt(i + 1) -> j in [0, i] INCLUSIVE
             *  using nextInt(n) here (a fixed bound) makes it NON-uniform
             */
            int j = rand.nextInt(i + 1);
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        return a;
    }
}

# python
# LC 384. Shuffle an Array
# IDEA: FISHER-YATES
# time = O(n) per shuffle, space = O(n)
import random

class Solution(object):
    def __init__(self, nums):
        self.original = nums[:]

    def reset(self):
        return self.original[:]

    def shuffle(self):
        arr = self.original[:]
        for i in range(len(arr) - 1, 0, -1):
            ### NOTE !!! randint is INCLUSIVE on both ends -> j in [0, i]
            j = random.randint(0, i)
            arr[i], arr[j] = arr[j], arr[i]
        return arr

w       = [1, 3, 2]
prefix  = [1, 4, 6]      total = 6

target: 1        -> idx 0   (prob 1/6)
        2,3,4    -> idx 1   (prob 3/6)
        5,6      -> idx 2   (prob 2/6)

// java
// LC 528 - Random Pick with Weight
// IDEA: PREFIX SUM + BINARY SEARCH (leftmost prefix >= target)
// time = O(n) build / O(log n) per pick, space = O(n)
class Solution {
    private final int[] prefix;
    private final int total;
    private final Random rand = new Random();

    public Solution(int[] w) {
        prefix = new int[w.length];
        int s = 0;
        for (int i = 0; i < w.length; i++) {
            s += w[i];
            prefix[i] = s;
        }
        total = s;
    }

    public int pickIndex() {
        /** NOTE !!! target in [1, total] (nextInt is exclusive on the bound) */
        int target = rand.nextInt(total) + 1;

        int lo = 0, hi = prefix.length - 1;
        while (lo < hi) {               // lower-bound style: NO `lo <= hi`
            int mid = lo + (hi - lo) / 2;
            if (prefix[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;               // NOTE: hi = mid (not mid - 1)
            }
        }
        return lo;
    }
}

# python
# LC 528. Random Pick with Weight
# IDEA: PREFIX SUM + BINARY SEARCH (leftmost prefix >= target)
# time = O(n) build / O(log n) per pick, space = O(n)
import random

class Solution(object):
    def __init__(self, w):
        self.prefix = []
        s = 0
        for x in w:
            s += x
            self.prefix.append(s)
        self.total = s

    def pickIndex(self):
        target = random.randint(1, self.total)   # inclusive [1, total]
        lo, hi = 0, len(self.prefix) - 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if self.prefix[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

# builtin shortcut (still O(log n)): bisect.bisect_left(self.prefix, target)

Proof for k = 3 items:
  P(keep #3) = 1/3
  P(keep #2) = 1/2 * (1 - 1/3) = 1/2 * 2/3 = 1/3
  P(keep #1) = 1   * (1 - 1/2) * (1 - 1/3) = 1/2 * 2/3 = 1/3   ✅ uniform

// java
// LC 398 - Random Pick Index
// IDEA: RESERVOIR SAMPLING (keep the k-th match with prob 1/k)
// time = O(n) per pick, space = O(1) extra
class Solution {
    private final int[] nums;
    private final Random rand = new Random();

    public Solution(int[] nums) {
        this.nums = nums;
    }

    public int pick(int target) {
        int count = 0, res = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != target) {
                continue;
            }
            count++;
            /** NOTE !!! nextInt(count) == 0 happens with prob 1/count */
            if (rand.nextInt(count) == 0) {
                res = i;
            }
        }
        return res;
    }
}

# python
# LC 398. Random Pick Index
# IDEA: RESERVOIR SAMPLING (keep the k-th match with prob 1/k)
# time = O(n) per pick, space = O(1) extra
import random

class Solution(object):
    def __init__(self, nums):
        self.nums = nums

    def pick(self, target):
        count = 0
        res = -1
        for i, v in enumerate(self.nums):
            if v != target:
                continue
            count += 1
            ### NOTE !!! keep index i with probability 1 / count
            if random.randint(1, count) == 1:
                res = i
        return res

arr = [a, b, c, d]      idx = {a:0, b:1, c:2, d:3}
remove(b):
  1) move last (d) into b's slot ->  arr = [a, d, c, d]  idx[d] = 1
  2) pop the tail               ->  arr = [a, d, c]
  3) drop b from the map        ->  idx = {a:0, d:1, c:2}   ✅ still dense

// java
// LC 380 - Insert Delete GetRandom O(1)
// IDEA: ARRAY (dense) + MAP (val -> index), delete by SWAP-WITH-LAST
// time = O(1) all ops, space = O(n)
class RandomizedSet {
    private final List<Integer> arr = new ArrayList<>();
    private final Map<Integer, Integer> idx = new HashMap<>();   // val -> position
    private final Random rand = new Random();

    public boolean insert(int val) {
        if (idx.containsKey(val)) {
            return false;
        }
        idx.put(val, arr.size());
        arr.add(val);
        return true;
    }

    public boolean remove(int val) {
        Integer i = idx.get(val);
        if (i == null) {
            return false;
        }
        /** NOTE !!! move the LAST element into the hole, then pop the tail */
        int last = arr.get(arr.size() - 1);
        arr.set(i, last);
        idx.put(last, i);
        arr.remove(arr.size() - 1);   // remove by INDEX -> O(1)
        idx.remove(val);              // NOTE: remove val AFTER the put above
        return true;
    }

    public int getRandom() {
        return arr.get(rand.nextInt(arr.size()));
    }
}

# python
# LC 380. Insert Delete GetRandom O(1)
# IDEA: ARRAY (dense) + MAP (val -> index), delete by SWAP-WITH-LAST
# time = O(1) all ops, space = O(n)
import random

class RandomizedSet(object):
    def __init__(self):
        self.arr = []
        self.idx = {}                 # val -> position in arr

    def insert(self, val):
        if val in self.idx:
            return False
        self.idx[val] = len(self.arr)
        self.arr.append(val)
        return True

    def remove(self, val):
        if val not in self.idx:
            return False
        ### NOTE !!! overwrite the hole with the last element, then pop
        i = self.idx[val]
        last = self.arr[-1]
        self.arr[i] = last
        self.idx[last] = i
        self.arr.pop()
        del self.idx[val]             # NOTE: delete AFTER re-pointing `last`
        return True

    def getRandom(self):
        return self.arr[random.randint(0, len(self.arr) - 1)]

# 168 Excel Sheet Column Title
# https://leetcode.com/problems/excel-sheet-column-title/discuss/205987/Python-Solution-with-explanation

# V0
# https://www.jianshu.com/p/591d3a2ab45d
class Solution(object):
    def convertToTitle(self, n):
        tar = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        res = ""
        while n > 0:
            # why (n-1) ? : idx start from 0
            m = (n-1) % 26
            #result += tar[m]
            res = (tar[m] + res)
            if m == 0:
                # why n=n+1 ? : since there is no 0 residual (m = (n-1) % 26), so we need to "pass" this case
                n = n + 1
            n = (n-1) // 26
        return res
# V0'
class Solution:
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        d='0ABCDEFGHIJKLMNOPQRSTUVWXYZ'
        res=''
        if n<=26:
            return d[n]
        else:
            while n > 0:
                n,r=divmod(n,26)
                # This is the catcha on this problem where when r==0 as a result of n%26. eg, n=52//26=2, r=52%26=0. 
                #To get 'AZ' as known for 52, n-=1 and r+=26. Same goes to 702.
                if r == 0:
                    n-=1
                    r+=26
                res = d[r] + res
        return res

// java
// LC 171 - Excel Sheet Column Number
// IDEA: BASE-26 HORNER (A..Z == 1..26, i.e. "bijective base 26")
// time = O(n), space = O(1)
public int titleToNumber(String columnTitle) {
    int res = 0;
    for (char ch : columnTitle.toCharArray()) {
        /** NOTE !!! `+ 1` -> 'A' is 1 (NOT 0); that is why 168 needs the -1 fixup */
        res = res * 26 + (ch - 'A' + 1);
    }
    return res;
}

# python
# LC 171. Excel Sheet Column Number
# IDEA: BASE-26 HORNER (A..Z == 1..26)
# time = O(n), space = O(1)
class Solution(object):
    def titleToNumber(self, columnTitle):
        res = 0
        for ch in columnTitle:
            ### NOTE !!! 'A' maps to 1, not 0
            res = res * 26 + (ord(ch) - ord('A') + 1)
        return res

# "A"  -> 1
# "AB" -> 1*26 + 2  = 28
# "ZY" -> 26*26 + 25 = 701

encode (168):  n -> title    needs  (n-1) % 26  and  n = (n-1) // 26
                             because a "digit" of 26 (Z) must borrow from the next place

decode (171):  title -> n    no fixup: res = res*26 + d,  d in [1, 26]

# LC 640. Solve the Equation
# V0
# IDEA : replace + eval + math
# https://leetcode.com/problems/solve-the-equation/discuss/105362/Simple-2-liner-(and-more)
# eval : The eval() method parses the expression passed to this method and runs python expression (code) within the program.
# -> https://www.runoob.com/python/python-func-eval.html
class Solution(object):
    def solveEquation(self, equation):
        tmp = equation.replace('x', 'j').replace('=', '-(')
        z = eval(tmp + ")" , {'j':1j})
        # print ("equation = " + str(equation))
        # print ("tmp = " + str(tmp))
        # print ("z = " + str(z))
        a, x = z.real, -z.imag
        return 'x=%d' % (a / x) if x else 'No solution' if a else 'Infinite solutions'

// java
// LC 13

// V0-1
// IDEA: MAP + STR OP (fixed by gpt)
public int romanToInt_0_1(String s) {
    if (s == null || s.isEmpty()) {
        return 0;
    }

    Map<Character, Integer> map = new HashMap<>();
    map.put('I', 1);
    map.put('V', 5);
    map.put('X', 10);
    map.put('L', 50);
    map.put('C', 100);
    map.put('D', 500);
    map.put('M', 1000);

    int total = 0;
    int prev = 0;

    /**
     * NOTE !!!
     *
     * loop reversely (from  idx = s.len() - 1)
     */
    for (int i = s.length() - 1; i >= 0; i--) {
        int curr = map.get(s.charAt(i));
        if (curr < prev) {
            total -= curr;
        } else {
            total += curr;
        }
        /**
         * NOTE !!!
         *
         *  set `prev` as curr
         */
        prev = curr;
    }

    return total;
}

// java
// LC 12 - Integer to Roman
// IDEA: GREEDY over a DESCENDING value table that already contains 900/400/90/40/9/4
// time = O(1) (num <= 3999), space = O(1)
public String intToRoman(int num) {
    /** NOTE !!! subtractive pairs are baked into the table -> no special cases */
    int[] vals    = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] syms = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < vals.length && num > 0; i++) {
        // take the biggest symbol that still fits, as many times as possible
        while (num >= vals[i]) {
            num -= vals[i];
            sb.append(syms[i]);
        }
    }
    return sb.toString();
}

# python
# LC 12. Integer to Roman
# IDEA: GREEDY over a DESCENDING value table (subtractive forms included)
# time = O(1) (num <= 3999), space = O(1)
class Solution(object):
    def intToRoman(self, num):
        vals = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

        res = []
        for v, s in zip(vals, syms):
            if num == 0:
                break
            ### NOTE !!! divmod gives "how many of this symbol" in one step
            cnt, num = divmod(num, v)
            res.append(s * cnt)
        return "".join(res)

# 3749 -> "MMMDCCXLIX"
# 1994 -> "MCMXCIV"
#    4 -> "IV"