Math

Last updated: Jul 28, 2026

Table of Contents

Math

1) General form

1-1) Basic OP

1-1-0) transform 10 based interger to N based

  • to 4 base
  • to 7 base …

```python # python # 504. Base 7

V0

IDEA : MATH : 10 based -> 7 based

“”"

NOTE :

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]

“”"

V1

class Solution(object): def convertToBase7(self, num): # edge case if num == 0: return ‘0’ tmp = abs(num) res = [] while tmp > 0: a, b = divmod(tmp, 7) res.append(str(b)) tmp = a res = res[::-1] _res = “”.join(res) if num > 0: return _res else: return “-” + _res

test

#----------------

exmaple :

7 base

20 -> 26

-100 -> -202

#---------------- num = 20 # 26 num = -100 # -202 s = Solution() r = s.convertToBase7(num) print ®

V2

https://www.itread01.com/content/1544603062.html

https://kknews.cc/code/jlv38qp.html

class Solution(object): def convertToBase7(self, num): # edge case if num == 0: return ‘0’ tmp = abs(num) res = [] while tmp: i = tmp % 7 res.append(str(i)) tmp = tmp // 7 res = res[::-1] _res = “”.join(res) if num > 0: return _res else: return “-” + _res


#### 1-1-0') transform `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

1-1-1) check prime number

python
# 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

1-1-2) count prime number

python
# 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
// 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
// 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;
}

1-1-3) Keep Remainder to Avoid Overflow (Repunit / Modular Arithmetic)

Core Idea: When building a number digit-by-digit (e.g. 1 → 11 → 111 → …), the number grows exponentially and overflows int/long. Instead of storing the full number, only keep the remainder mod k at each step.

This works because:

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

So the remainder after adding a new digit can always be computed from the previous remainder alone.

Pattern:

java
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;

Key insight — Pigeonhole Principle: There are only k possible remainders (0 to k-1). After k steps, if no remainder is 0, a remainder must repeat → cycle with no solution → return -1. So we only need to loop up to k times.

Quick check — early exit: A number made only of 1s never ends in 0, 2, 4, 5, 6, or 8, so it can never be divisible by 2 or 5:

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

Similar LC problems using this remainder trick:

Problem Pattern
LC 1015 - Smallest Integer Divisible by K repunit mod k
LC 29 - Divide Two Integers avoid overflow with bit ops
LC 166 - Fraction to Recurring Decimal detect cycle via remainder map
LC 523 - Continuous Subarray Sum prefix sum mod k
LC 974 - Subarray Sums Divisible by K prefix sum mod k
java
// 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;
}

1-1-4) Check if 4 points form a valid square (Pairwise Distance Trick)

Core Idea: Given 4 points in any order, checking angles/slopes directly is messy (division by zero, floating point). Instead, compute the 6 pairwise squared distances among the 4 points and reason about them as a multiset.

Why 6 distances? 4 points → C(4,2) = 6 pairs. For a square:

text
A ----- B
|       |
|       |
D ----- C
text
AB = side
BC = side
CD = side
DA = side
AC = diagonal
BD = diagonal

So after sorting the 6 squared distances, you always get 4 equal (smaller) values + 2 equal (larger) values.

Pattern — a valid square has:

  • side > 0 (no overlapping points)
  • 4 equal sides
  • 2 equal diagonals
  • diagonal > side
python
# 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

Alternative (set-based) form: Since a valid square has exactly 2 distinct distance values (side², diagonal²), and diagonal is always > side for a real square, you can just check len(set(distances)) == 2 (plus the 0 not in distances guard for overlapping points):

python
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

1-1-5) Weighted Rotation Sum — Telescoping Recurrence (avoid O(n²) brute force)

Pattern: Brute-force recomputing F(k) = sum(i * arr_k[i]) for every rotation k costs O(n) per rotation → O(n²) total. Instead, derive an O(1) transition from F(k-1) to F(k) and slide through all n rotations in O(n).

Core Idea: Write out a few rotations by hand and compare term by term (nums = [A, B, C, D], n = 4):

text
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

Every element’s weight goes up by 1 when you rotate — except the element that just wrapped from the back to the front, whose weight drops from n-1 down to 0. So:

text
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

Generalizing, the element that wraps into position 0 for F(k) is nums[n-k], giving the recurrence:

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

This is the same “maintain a running aggregate instead of recomputing from scratch” philosophy as prefix sums — just applied to a weighted sum instead of a plain sum.

python
# 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

Similar LC problems (same “O(1) transition between states” idea):

Problem Pattern
LC 396 - Rotate Function telescoping weighted-sum recurrence: F(k) = F(k-1) + sum - n*nums[n-k]
LC 238 - Product of Array Except Self running prefix/suffix product instead of recomputing per index
LC 303 - Range Sum Query - Immutable precomputed prefix sum instead of recomputing per query
LC 189 - Rotate Array actual physical rotation (reverse trick) — contrast: no aggregate formula, just rearranges elements

2) LC Example

2-1) Excel Sheet Column Title — LC 168

python
# 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

2-2) Solve the Equation — LC 640

python
# 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'

2-3) Roman to Integer — LC 13

java
// 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;
}
← Back to Cheat Sheets Edit on GitHub →