Problems

Master the math algorithms pattern by solving these carefully selected problems. Each problem demonstrates a different mathematical concept and builds your problem-solving skills progressively. For a refresher on the core templates used in these solutions, check out the Code Templates.

Problem Categories

Easy Problems

1. Reverse Integer

Brief: Given a signed 32-bit integer x, return x with its digits reversed, returning 0 if the reversed integer would overflow.
Why this pattern?: This problem requires careful digit manipulation and overflow detection, common in integer-based mathematical algorithms.
Key Insight: Extract digits using modulo 10, but check for overflow before multiplying the result by 10 to prevent integer overflow.

Visual:

  graph TD
    Start[Start with x = 123]
    Extract[digit = 123 % 10 = 3]
    Divide[x = 123 / 10 = 12]
    Check{rev * 10 + digit > INT_MAX?}
    Check -->|Yes| Return[Return 0 - overflow]
    Check -->|No| Multiply[rev = rev * 10 + digit]
    Multiply --> Loop{x != 0?}
    Loop -->|Yes| Extract
    Loop -->|No| Done[Return rev]

Code Solution:

JavaScript:

function reverse(x) {
    const INT_MAX = 2147483647;
    const INT_MIN = -2147483648;
    let rev = 0;

    while (x !== 0) {
        const digit = x % 10;
        x = x > 0 ? Math.floor(x / 10) : Math.ceil(x / 10);

        // Check for overflow before adding next digit
        if (rev > INT_MAX / 10 || (rev === INT_MAX / 10 && digit > 7)) return 0;
        if (rev < INT_MIN / 10 || (rev === INT_MIN / 10 && digit < -8)) return 0;

        rev = rev * 10 + digit;
    }

    return rev;
}

Python:

def reverse(x: int) -> int:
    INT_MAX = 2147483647
    INT_MIN = -2147483648
    rev = 0

    while x != 0:
        digit = x % 10
        x = x // 10 if x > 0 else -(-x // 10)  # Ceiling division for negative

        # Check for overflow before adding next digit
        if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and digit > 7):
            return 0
        if rev < INT_MIN // 10 or (rev == INT_MIN // 10 and digit < -8):
            return 0

        rev = rev * 10 + digit

    return rev

Java:

public class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int digit = x % 10;
            x /= 10;

            // Check for overflow before adding next digit
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && digit < -8)) return 0;

            rev = rev * 10 + digit;
        }
        return rev;
    }
}

C++:

class Solution {
public:
    int reverse(int x) {
        long long rev = 0;
        while (x != 0) {
            int digit = x % 10;
            x /= 10;

            // Check for overflow before adding next digit
            if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && digit > 7)) return 0;
            if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && digit < -8)) return 0;

            rev = rev * 10 + digit;
        }
        return (int)rev;
    }
};

Go:

func reverse(x int) int {
    const INT_MAX = 2147483647
    const INT_MIN = -2147483648
    rev := 0

    for x != 0 {
        digit := x % 10
        x /= 10

        // Check for overflow before adding next digit
        if rev > INT_MAX/10 || (rev == INT_MAX/10 && digit > 7) {
            return 0
        }
        if rev < INT_MIN/10 || (rev == INT_MIN/10 && digit < -8) {
            return 0
        }

        rev = rev*10 + digit
    }

    return rev
}

Ruby:

def reverse(x)
  int_max = 2147483647
  int_min = -2147483648
  rev = 0

  while x != 0
    digit = x % 10
    x = x > 0 ? x / 10 : (x / 10.0).ceil

    # Check for overflow before adding next digit
    if rev > int_max / 10 || (rev == int_max / 10 && digit > 7)
      return 0
    end
    if rev < int_min / 10 || (rev == int_min / 10 && digit < -8)
      return 0
    end

    rev = rev * 10 + digit
  end

  rev
end

Time Complexity:

O(log n)

| Space Complexity:

O(1)

2. Palindrome Number

Brief: Determine if an integer is a palindrome without converting it to a string.
Why this pattern?: This requires reversing half the number and comparing, using mathematical operations instead of string manipulation.
Key Insight: Reverse only the second half of the number and compare with the first half to avoid overflow issues.

Visual:

  graph TD
    Start[x = 121]
    Check1{x < 0 or x % 10 == 0 and x != 0?}
    Check1 -->|Yes| False[Return false]
    Check1 -->|No| Loop[x > reversed?]
    Loop -->|Yes| Reverse[reversed = reversed * 10 + x % 10<br>x = x / 10]
    Loop -->|No| Compare{x == reversed or x == reversed / 10?}
    Compare -->|Yes| True[Return true]
    Compare -->|No| False

Code Solution:

JavaScript:

function isPalindrome(x) {
    // Negative numbers and numbers ending with 0 (except 0) are not palindromes
    if (x < 0 || (x % 10 === 0 && x !== 0)) {
        return false;
    }

    let reversed = 0;
    while (x > reversed) {
        reversed = reversed * 10 + x % 10;
        x = Math.floor(x / 10);
    }

    // For even length, compare directly
    // For odd length, ignore middle digit in reversed
    return x === reversed || x === Math.floor(reversed / 10);
}

Python:

def isPalindrome(x: int) -> bool:
    # Negative numbers and numbers ending with 0 (except 0) are not palindromes
    if x < 0 or (x % 10 == 0 and x != 0):
        return False

    reversed_num = 0
    while x > reversed_num:
        reversed_num = reversed_num * 10 + x % 10
        x = x // 10

    # For even length, compare directly
    # For odd length, ignore middle digit in reversed
    return x == reversed_num or x == reversed_num // 10

Java:

public class Solution {
    public boolean isPalindrome(int x) {
        // Negative numbers and numbers ending with 0 (except 0) are not palindromes
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversed = 0;
        while (x > reversed) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }

        // For even length, compare directly
        // For odd length, ignore middle digit in reversed
        return x == reversed || x == reversed / 10;
    }
}

C++:

class Solution {
public:
    bool isPalindrome(int x) {
        // Negative numbers and numbers ending with 0 (except 0) are not palindromes
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversed = 0;
        while (x > reversed) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }

        // For even length, compare directly
        // For odd length, ignore middle digit in reversed
        return x == reversed || x == reversed / 10;
    }
};

Go:

func isPalindrome(x int) bool {
    // Negative numbers and numbers ending with 0 (except 0) are not palindromes
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }

    reversed := 0
    for x > reversed {
        reversed = reversed*10 + x%10
        x /= 10
    }

    // For even length, compare directly
    // For odd length, ignore middle digit in reversed
    return x == reversed || x == reversed/10
}

Ruby:

def is_palindrome(x)
  # Negative numbers and numbers ending with 0 (except 0) are not palindromes
  return false if x < 0 || (x % 10 == 0 && x != 0)

  reversed = 0
  while x > reversed
    reversed = reversed * 10 + x % 10
    x /= 10
  end

  # For even length, compare directly
  # For odd length, ignore middle digit in reversed
  x == reversed || x == reversed / 10
end

Time Complexity:

O(log n)

| Space Complexity:

O(1)

3. Plus One

Brief: Increment a large integer represented as an array of digits by one.
Why this pattern?: Demonstrates digit-by-digit arithmetic and carry propagation, fundamental to mathematical string/array algorithms.
Key Insight: Start from the end; if a digit is 9, turn it to 0 and continue. If it’s less than 9, increment and we’re done.

Visual:

  graph LR
    Input[9, 9] --> D1[Add 1 to 9]
    D1 --> C1[Result 0, Carry 1]
    C1 --> D2[Add 1 to 9]
    D2 --> C2[Result 0, Carry 1]
    C2 --> New[Insert 1 at start]
    New --> Final[1, 0, 0]

Code Solution:

JavaScript:

function plusOne(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }
    digits.unshift(1);
    return digits;
}

Python:

def plusOne(digits: List[int]) -> List[int]:
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

Java:

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        return result;
    }
}

C++:

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

Go:

func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }
    return append([]int{1}, digits...)
}

Ruby:

def plus_one(digits)
  (digits.length - 1).downto(0) do |i|
    if digits[i] < 9
      digits[i] += 1
      return digits
    end
    digits[i] = 0
  end
  [1] + digits
end

Time Complexity:

O(N)

| Space Complexity:

O(1)

(excluding output)

4. Excel Sheet Column Number

Brief: Convert an Excel column title (A, B, C…) to its corresponding integer.
Why this pattern?: A classic base-conversion problem (base-26).
Key Insight: Process characters from left to right, multiplying the current result by 26 and adding the value of the current character.

Visual:

  graph LR
    Input["AB"] --> A["Val 1 (A)"]
    A --> Step1["1 * 26 + 2 (B)"]
    Step1 --> Final["Result: 28"]

Code Solution:

JavaScript:

function titleToNumber(columnTitle) {
    let result = 0;
    for (let i = 0; i < columnTitle.length; i++) {
        const d = columnTitle.charCodeAt(i) - 64;
        result = result * 26 + d;
    }
    return result;
}

Python:

def titleToNumber(columnTitle: str) -> int:
    result = 0
    for char in columnTitle:
        d = ord(char) - ord('A') + 1
        result = result * 26 + d
    return result

Java:

class Solution {
    public int titleToNumber(String columnTitle) {
        int result = 0;
        for (char c : columnTitle.toCharArray()) {
            int d = c - 'A' + 1;
            result = result * 26 + d;
        }
        return result;
    }
}

C++:

class Solution {
public:
    int titleToNumber(string columnTitle) {
        long long result = 0;
        for (char c : columnTitle) {
            int d = c - 'A' + 1;
            result = result * 26 + d;
        }
        return (int)result;
    }
};

Go:

func titleToNumber(columnTitle string) int {
    result := 0
    for _, char := range columnTitle {
        d := int(char - 'A' + 1)
        result = result*26 + d
    }
    return result
}

Ruby:

def title_to_number(column_title)
  result = 0
  column_title.each_char do |char|
    d = char.ord - 'A'.ord + 1
    result = result * 26 + d
  end
  result
end

Time Complexity:

O(N)

| Space Complexity:

O(1)

5. Ugly Number

Brief: Check if a number’s prime factors are only 2, 3, or 5.
Why this pattern?: Demonstrates prime factor reduction using repeated division.
Key Insight: Repeatedly divide by 2, 3, and 5 as long as possible. If the remaining number is 1, it was ugly.

Visual:

  graph TD
    Start[n = 30] --> D2[Div by 2: 15]
    D2 --> D3[Div by 3: 5]
    D3 --> D5[Div by 5: 1]
    D5 --> Check{1 == 1?}
    Check -->|Yes| Ugly[Ugly!]

Code Solution:

JavaScript:

function isUgly(n) {
    if (n <= 0) return false;
    for (let factor of [2, 3, 5]) {
        while (n % factor === 0) {
            n /= factor;
        }
    }
    return n === 1;
}

Python:

def isUgly(n: int) -> bool:
    if n <= 0:
        return False
    for factor in [2, 3, 5]:
        while n % factor == 0:
            n //= factor
    return n == 1

Java:

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        int[] factors = {2, 3, 5};
        for (int f : factors) {
            while (n % f == 0) n /= f;
        }
        return n == 1;
    }
}

C++:

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) return false;
        vector<int> factors = {2, 3, 5};
        for (int f : factors) {
            while (n % f == 0) n /= f;
        }
        return n == 1;
    }
};

Go:

func isUgly(n int) bool {
    if n <= 0 {
        return false
    }
    for _, f := range []int{2, 3, 5} {
        for n%f == 0 {
            n /= f
        }
    }
    return n == 1
}

Ruby:

def is_ugly(n)
  return false if n <= 0
  [2, 3, 5].each do |f|
    n /= f while n % f == 0
  end
  n == 1
end

Time Complexity:

O(log n)

| Space Complexity:

O(1)

6. Valid Perfect Square

Brief: Determine if a number is a perfect square without using built-in sqrt.
Why this pattern?: Combines mathematical properties with binary search.
Key Insight: Search for x such that x*x == num in the range [1, num].

Visual:

  graph LR
    Range[1...16] --> Mid[Mid 8: 64 > 16]
    Mid --> Range2[1...7]
    Range2 --> Mid2[Mid 4: 16 == 16]
    Mid2 --> Found[True]

Code Solution:

JavaScript:

function isPerfectSquare(num) {
    let left = 1, right = num;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let sq = mid * mid;
        if (sq === num) return true;
        if (sq < num) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

Python:

def isPerfectSquare(num: int) -> bool:
    left, right = 1, num
    while left <= right:
        mid = (left + right) // 2
        sq = mid * mid
        if sq == num:
            return True
        if sq < num:
            left = mid + 1
        else:
            right = mid - 1
    return False

Java:

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1, right = num;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long sq = mid * mid;
            if (sq == num) return true;
            if (sq < num) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
}

C++:

class Solution {
public:
    bool isPerfectSquare(int num) {
        long long left = 1, right = num;
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            long long sq = mid * mid;
            if (sq == num) return true;
            if (sq < num) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

Go:

func isPerfectSquare(num int) bool {
    left, right := 1, num
    for left <= right {
        mid := left + (right-left)/2
        sq := mid * mid
        if sq == num {
            return true
        }
        if sq < num {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

Ruby:

def is_perfect_square(num)
  left, right = 1, num
  while left <= right
    mid = (left + right) / 2
    sq = mid * mid
    return true if sq == num
    if sq < num
      left = mid + 1
    else
      right = mid - 1
    end
  end
  false
end

Time Complexity:

O(log n)

| Space Complexity:

O(1)

7. Arranging Coins

Brief: Find the number of complete rows in a staircase built with n coins.
Why this pattern?: Solves a quadratic sum formula k(k+1)/2 <= n.
Key Insight: Can be solved using the quadratic formula k = (sqrt(8n + 1) - 1) / 2 or binary search.

Visual:

  graph TD
    n5[n = 5] --> Row1[Row 1: 1 coin]
    Row1 --> Row2[Row 2: 2 coins]
    Row2 --> Row3[Row 3: Need 3, have 2剩下]
    Row3 --> Final[Complete Rows: 2]

Code Solution:

JavaScript:

function arrangeCoins(n) {
    return Math.floor((Math.sqrt(8 * n + 1) - 1) / 2);
}

Python:

import math
def arrangeCoins(n: int) -> int:
    return int((math.sqrt(8 * n + 1) - 1) / 2)

Java:

class Solution {
    public int arrangeCoins(int n) {
        return (int)((Math.sqrt(8.0 * n + 1) - 1) / 2);
    }
}

C++:

class Solution {
public:
    int arrangeCoins(int n) {
        return (int)((sqrt(8.0 * n + 1) - 1) / 2);
    }
};

Go:

import "math"
func arrangeCoins(n int) int {
    return int((math.Sqrt(float64(8*n+1)) - 1) / 2)
}

Ruby:

def arrange_coins(n)
  ((Math.sqrt(8 * n + 1) - 1) / 2).to_i
end

Time Complexity:

O(1)

(using formula) or

O(log n)

(using binary search)

8. Perfect Number

Brief: Check if a number is equal to the sum of its positive divisors excluding itself.
Why this pattern?: Demonstrates efficient divisor finding in O(sqrt(n)).
Key Insight: Divisors come in pairs. If i divides n, then n/i is also a divisor. Summ them up to sqrt(n).

Visual:

  graph TD
    n28[n = 28] --> D1[1]
    n28 --> D2[2 & 14]
    n28 --> D4[4 & 7]
    D1 & D2 & D4 --> Sum[1 + 2 + 14 + 4 + 7 = 28]
    Sum --> Match[Result: True]

Code Solution:

JavaScript:

function checkPerfectNumber(num) {
    if (num <= 1) return false;
    let sum = 1;
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) {
            sum += i;
            if (i * i !== num) sum += num / i;
        }
    }
    return sum === num;
}

Python:

def checkPerfectNumber(num: int) -> bool:
    if num <= 1:
        return False
    total = 1
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            total += i
            if i * i != num:
                total += num // i
    return total == num

Java:

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) return false;
        int sum = 1;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) sum += num / i;
            }
        }
        return sum == num;
    }
}

C++:

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 1) return false;
        int sum = 1;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) sum += num / i;
            }
        }
        return sum == num;
    }
};

Go:

func checkPerfectNumber(num int) bool {
    if num <= 1 {
        return false
    }
    sum := 1
    for i := 2; i*i <= num; i++ {
        if num%i == 0 {
            sum += i
            if i*i != num {
                sum += num / i
            }
        }
    }
    return sum == num
}

Ruby:

def check_perfect_number(num)
  return false if num <= 1
  sum = 1
  (2..Integer.sqrt(num)).each do |i|
    if num % i == 0
      sum += i
      sum += num / i if i * i != num
    end
  end
  sum == num
end

Time Complexity:

O(sqrt(n))

| Space Complexity:

O(1)

9. Excel Sheet Column Title

Brief: Given an integer, return its corresponding Excel column title (1 -> A, 2 -> B, 26 -> Z, 27 -> AA…).
Why this pattern?: Reverse base-26 conversion with a 1-based offset.
Key Insight: Similar to base conversion, but since it’s 1-indexed, we subtract 1 from the number before taking the modulo 26.

Visual:

  graph LR
    n28[n = 28] --> S1[28 - 1 = 27]
    S1 --> R1[27 % 26 = 1 -> 'B']
    R1 --> S2[27 / 26 = 1]
    S2 --> S3[1 - 1 = 0]
    S3 --> R2[0 % 26 = 0 -> 'A']
    R2 --> Final[Result: AB]

Code Solution:

JavaScript:

function convertToTitle(columnNumber) {
    let result = "";
    while (columnNumber > 0) {
        columnNumber--;
        result = String.fromCharCode((columnNumber % 26) + 65) + result;
        columnNumber = Math.floor(columnNumber / 26);
    }
    return result;
}

Python:

def convertToTitle(columnNumber: int) -> str:
    result = []
    while columnNumber > 0:
        columnNumber -= 1
        result.append(chr(columnNumber % 26 + ord('A')))
        columnNumber //= 26
    return "".join(result[::-1])

Java:

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        while (columnNumber > 0) {
            columnNumber--;
            sb.append((char)('A' + columnNumber % 26));
            columnNumber /= 26;
        }
        return sb.reverse().toString();
    }
}

C++:

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string res = "";
        while (columnNumber > 0) {
            columnNumber--;
            res += (char)('A' + columnNumber % 26);
            columnNumber /= 26;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Go:

func convertToTitle(columnNumber int) string {
    result := ""
    for columnNumber > 0 {
        columnNumber--
        result = string('A'+(columnNumber%26)) + result
        columnNumber /= 26
    }
    return result
}

Ruby:

def convert_to_title(column_number)
  result = ""
  while column_number > 0
    column_number -= 1
    result = (('A'.ord + column_number % 26).chr) + result
    column_number /= 26
  end
  result
end

Time Complexity:

O(log₂₆ n)

| Space Complexity:

O(1)

(excluding output string)

10. Add Strings

Brief: Add two non-negative integers represented as strings.
Why this pattern?: Classic “BigInt” addition logic using pointers and carry.
Key Insight: Use two pointers starting from the end of both strings. Maintain a carry and process digit by digit.

Visual:

  graph LR
    s1["123"]
    s2["456"]
    s1 & s2 --> Add3[3 + 6 = 9]
    Add3 --> Add2[2 + 5 = 7]
    Add2 --> Add1[1 + 4 = 5]
    Add1 --> Final["579"]

Code Solution:

JavaScript:

function addStrings(num1, num2) {
    let i = num1.length - 1, j = num2.length - 1, carry = 0, res = "";
    while (i >= 0 || j >= 0 || carry) {
        let n1 = i >= 0 ? num1[i--] - '0' : 0;
        let n2 = j >= 0 ? num2[j--] - '0' : 0;
        let val = n1 + n2 + carry;
        res = (val % 10) + res;
        carry = Math.floor(val / 10);
    }
    return res;
}

Python:

def addStrings(num1: str, num2: str) -> str:
    i, j, carry, res = len(num1) - 1, len(num2) - 1, 0, []
    while i >= 0 or j >= 0 or carry:
        n1 = int(num1[i]) if i >= 0 else 0
        n2 = int(num2[j]) if j >= 0 else 0
        carry, v = divmod(n1 + n2 + carry, 10)
        res.append(str(v))
        i, j = i - 1, j - 1
    return "".join(res[::-1])

Java:

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry != 0) {
            int n1 = i >= 0 ? num1.charAt(i--) - '0' : 0;
            int n2 = j >= 0 ? num2.charAt(j--) - '0' : 0;
            int sum = n1 + n2 + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }
}

C++:

class Solution {
public:
    string addStrings(string num1, string num2) {
        string res = "";
        int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry) {
            int n1 = i >= 0 ? num1[i--] - '0' : 0;
            int n2 = j >= 0 ? num2[j--] - '0' : 0;
            int sum = n1 + n2 + carry;
            res += to_string(sum % 10);
            carry = sum / 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Go:

import "strconv"

func addStrings(num1 string, num2 string) string {
    res := ""
    i, j, carry := len(num1)-1, len(num2)-1, 0
    for i >= 0 || j >= 0 || carry != 0 {
        n1, n2 := 0, 0
        if i >= 0 { n1 = int(num1[i] - '0'); i-- }
        if j >= 0 { n2 = int(num2[j] - '0'); j-- }
        sum := n1 + n2 + carry
        res = strconv.Itoa(sum%10) + res
        carry = sum / 10
    }
    return res
}

Ruby:

def add_strings(num1, num2)
  i, j, carry, res = num1.length - 1, num2.length - 1, 0, ""
  while i >= 0 || j >= 0 || carry > 0
    n1 = i >= 0 ? num1[i].to_i : 0
    n2 = j >= 0 ? num2[j].to_i : 0
    sum = n1 + n2 + carry
    res = (sum % 10).to_s + res
    carry = sum / 10
    i, j = i - 1, j - 1
  end
  res
end

Time Complexity:

O(max(N,M))

| Space Complexity:

O(1)

(excluding output string)

Medium Problems

11. Pow(x, n)

Brief: Implement pow(x, n), which calculates x raised to the power n.
Why this pattern?: Uses the Fast Exponentiation (Binary Exponentiation) template.
Key Insight: Divide the problem: x^n = (x * x)^(n/2). This reduces complexity from linear to logarithmic.

Visual:

  graph TD
    Start[2 ^ 10] --> Step1[4 ^ 5]
    Step1 --> Step2[4 * 16 ^ 2]
    Step2 --> Step3[4 * 256 ^ 1]
    Step3 --> Final[1024]

Code Solution:

JavaScript:

function myPow(x, n) {
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    let res = 1;
    while (n > 0) {
        if (n % 2 === 1) res *= x;
        x *= x;
        n = Math.floor(n / 2);
    }
    return res;
}

Python:

def myPow(x: float, n: int) -> float:
    if n < 0:
        x = 1 / x
        n = -n
    res = 1
    while n > 0:
        if n % 2 == 1:
            res *= x
        x *= x
        n //= 2
    return res

Java:

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double res = 1;
        while (N > 0) {
            if (N % 2 == 1) res *= x;
            x *= x;
            N /= 2;
        }
        return res;
    }
}

C++:

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double res = 1.0;
        while (N > 0) {
            if (N % 2 == 1) res *= x;
            x *= x;
            N /= 2;
        }
        return res;
    }
};

Go:

func myPow(x float64, n int) float64 {
    longN := int64(n)
    if longN < 0 {
        x = 1 / x
        longN = -longN
    }
    res := 1.0
    for longN > 0 {
        if longN%2 == 1 {
            res *= x
        }
        x *= x
        longN /= 2
    }
    return res
}

Ruby:

def my_pow(x, n)
  n_long = n
  if n_long < 0
    x = 1.0 / x
    n_long = -n_long
  end
  res = 1.0
  while n_long > 0
    res *= x if n_long.odd?
    x *= x
    n_long /= 2
  end
  res
end

Time Complexity:

O(log n)

| Space Complexity:

O(1)

12. Factorial Trailing Zeroes

Brief: Return the number of trailing zeroes in n!.
Why this pattern?: Number theory application - counting factors of 5.
Key Insight: A trailing zero is created by a pair of factors 2 and 5. In a factorial, factors of 2 are always more abundant than 5, so we just need to count how many times 5 is a factor in all numbers from 1 to n.

Visual:

  graph TD
    n25[n = 25] --> F5[Five multiples: 5, 10, 15, 20, 25]
    F5 --> C5[Count: 5]
    n25 --> F25[Twenty-five multiples: 25]
    F25 --> C25[Count: 1]
    C5 & C25 --> Total[Total Factors of 5: 6]

Code Solution:

JavaScript:

function trailingZeroes(n) {
    let count = 0;
    while (n >= 5) {
        count += Math.floor(n / 5);
        n = Math.floor(n / 5);
    }
    return count;
}

Python:

def trailingZeroes(n: int) -> int:
    count = 0
    while n >= 5:
        count += n // 5
        n //= 5
    return count

Java:

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n >= 5) {
            count += n / 5;
            n /= 5;
        }
        return count;
    }
}

C++:

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while (n >= 5) {
            count += n / 5;
            n /= 5;
        }
        return count;
    }
};

Go:

func trailingZeroes(n int) int {
    count := 0
    for n >= 5 {
        count += n / 5
        n /= 5
    }
    return count
}

Ruby:

def trailing_zeroes(n)
  count = 0
  while n >= 5
    count += n / 5
    n /= 5
  end
  count
end

Time Complexity:

O(log₅ n)

| Space Complexity:

O(1)

13. Bulb Switcher

Brief: Find how many bulbs are on after n rounds of toggling.
Why this pattern?: Pure mathematical insight problem.
Key Insight: A bulb i remains on if it’s toggled an odd number of times. This only happens if i has an odd number of divisors, which is the definition of a perfect square. The problem simply asks: how many perfect squares are there <= n?

Visual:

  graph LR
    n10[n = 10] --> Squares[1, 4, 9]
    Squares --> Count[Result: 3]

Code Solution:

JavaScript:

function bulbSwitch(n) {
    return Math.floor(Math.sqrt(n));
}

Python:

import math
def bulbSwitch(n: int) -> int:
    return int(math.sqrt(n))

Java:

class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}

C++:

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

Go:

import "math"
func bulbSwitch(n int) int {
    return int(math.Sqrt(float64(n)))
}

Ruby:

def bulb_switch(n)
  Integer.sqrt(n)
end

Time Complexity:

O(1)

| Space Complexity:

O(1)

14. Water and Jug Problem

Brief: Determine if you can measure exactly target liters using two jugs of capacity x and y.
Why this pattern?: Application of Bézout’s Identity and GCD.
Key Insight: It is possible to measure z liters if and only if z is a multiple of gcd(x, y) and z <= x + y.

Visual:

  graph TD
    Input[x=3, y=5, target=4] --> GCD[gcd 3, 5 = 1]
    GCD --> Check{4 % 1 == 0?}
    Check -->|Yes| True[Return True]

Code Solution:

JavaScript:

function canMeasureWater(x, y, target) {
    if (x + y < target) return false;
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    return target % gcd(x, y) === 0;
}

Python:

import math
def canMeasureWater(x: int, y: int, target: int) -> bool:
    if x + y < target:
        return False
    return target % math.gcd(x, y) == 0

Java:

class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        if (x + y < target) return false;
        return target % gcd(x, y) == 0;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

C++:

class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
        if (x + y < target) return false;
        return target % gcd(x, y) == 0;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

Go:

func canMeasureWater(x int, y int, target int) bool {
    if x+y < target {
        return false
    }
    return target%gcd(x, y) == 0
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

Ruby:

def can_measure_water(x, y, target)
  return false if x + y < target
  target % x.gcd(y) == 0
end

Time Complexity:

O(log(min(x,y)))

| Space Complexity:

O(1)

15. Sum of Square Numbers

Brief: Check if c can be represented as a² + b².
Why this pattern?: Standard search in mathematical ranges.
Key Insight: Use two pointers: a = 0 and b = sqrt(c). If a² + b² < c, increment a. If > c, decrement b.

Visual:

  graph LR
    c5[c = 5] --> Pointers[a=0, b=2]
    Pointers --> Step1[0^2 + 2^2 = 4 < 5]
    Step1 --> Step2[a=1, b=2]
    Step2 --> Final[1^2 + 2^2 = 5 == 5]

Code Solution:

JavaScript:

function judgeSquareSum(c) {
    let a = 0, b = Math.floor(Math.sqrt(c));
    while (a <= b) {
        let sum = a * a + b * b;
        if (sum === c) return true;
        if (sum < c) a++;
        else b--;
    }
    return false;
}

Python:

import math
def judgeSquareSum(c: int) -> bool:
    a, b = 0, int(math.sqrt(c))
    while a <= b:
        val = a * a + b * b
        if val == c:
            return True
        if val < c:
            a += 1
        else:
            b -= 1
    return False

Java:

class Solution {
    public boolean judgeSquareSum(int c) {
        long a = 0, b = (long)Math.sqrt(c);
        while (a <= b) {
            long val = a * a + b * b;
            if (val == c) return true;
            if (val < c) a++;
            else b--;
        }
        return false;
    }
}

C++:

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long a = 0, b = sqrt(c);
        while (a <= b) {
            long long val = a * a + b * b;
            if (val == c) return true;
            if (val < c) a++;
            else b--;
        }
        return false;
    }
};

Go:

import "math"
func judgeSquareSum(c int) bool {
    a, b := 0, int(math.Sqrt(float64(c)))
    for a <= b {
        val := a*a + b*b
        if val == c {
            return true
        }
        if val < c {
            a++
        } else {
            b--
        }
    }
    return false
}

Ruby:

def judge_square_sum(c)
  a, b = 0, Integer.sqrt(c)
  while a <= b
    val = a * a + b * b
    return true if val == c
    if val < c
      a += 1
    else
      b -= 1
    end
  end
  false
end

Time Complexity:

O(sqrt(c))

| Space Complexity:

O(1)

Hard Problems

16. Find the Closest Palindrome

Brief: Given a string n, return the closest integer that is a palindrome.
Why this pattern?: Advanced digit manipulation and corner case handling.
Key Insight: There are 5 candidates for the closest palindrome:
1. Mirroring the first half (e.g., 123 -> 121)
2. Incrementing the first half and mirroring (e.g., 123 -> 131)
3. Decrementing the first half and mirroring (e.g., 123 -> 111)
4. Lower bound power of 10 (e.g., 100 -> 99)
5. Upper bound power of 10 (e.g., 99 -> 101)

Visual:

  graph TD
    Input["123"] --> C1["121 (Mirror)"]
    Input --> C2["131 (Half + 1)"]
    Input --> C3["111 (Half - 1)"]
    Input --> C4["99 (Edge)"]
    Input --> C5["101 (Edge)"]
    C1 & C2 & C3 & C4 & C5 --> Diff[Compare Diffs]
    Diff --> Result["121"]

Code Solution:

JavaScript:

function nearestPalindromic(n) {
    const len = n.length;
    const candidates = new Set();
    candidates.add((Math.pow(10, len - 1) - 1).toString());
    candidates.add((Math.pow(10, len) + 1).toString());

    const prefix = n.substring(0, Math.ceil(len / 2));
    for (let i of [-1, 0, 1]) {
        let p = (parseInt(prefix) + i).toString();
        let res;
        if (len % 2 === 0) res = p + p.split("").reverse().join("");
        else res = p + p.substring(0, p.length - 1).split("").reverse().join("");
        candidates.add(res);
    }

    candidates.delete(n);
    let minDiff = Infinity, result = "";
    for (let c of candidates) {
        let diff = Math.abs(BigInt(c) - BigInt(n));
        if (diff < minDiff || (diff === minDiff && BigInt(c) < BigInt(result))) {
            minDiff = diff;
            result = c;
        }
    }
    return result;
}

Python:

def nearestPalindromic(n: str) -> str:
    l = len(n)
    candidates = {str(10**(l-1)-1), str(10**l+1)}
    prefix = int(n[:(l+1)//2])
    for i in [-1, 0, 1]:
        p = str(prefix + i)
        if l % 2 == 0:
            candidates.add(p + p[::-1])
        else:
            candidates.add(p + p[:-1][::-1])

    candidates.discard(n)
    num_n = int(n)
    best = None
    for c in candidates:
        if best is None or abs(int(c) - num_n) < abs(int(best) - num_n) or \
           (abs(int(c) - num_n) == abs(int(best) - num_n) and int(c) < int(best)):
            best = c
    return best

Java:

import java.util.*;

class Solution {
    public String nearestPalindromic(String n) {
        int len = n.length();
        Set<Long> set = new HashSet<>();
        set.add((long)Math.pow(10, len - 1) - 1);
        set.add((long)Math.pow(10, len) + 1);
        long prefix = Long.parseLong(n.substring(0, (len + 1) / 2));
        for (long i : new long[]{-1, 0, 1}) {
            String p = String.valueOf(prefix + i);
            StringBuilder sb = new StringBuilder(p);
            if (len % 2 == 1) sb.deleteCharAt(sb.length() - 1);
            set.add(Long.parseLong(p + sb.reverse().toString()));
        }
        set.remove(Long.parseLong(n));
        long best = -1, numN = Long.parseLong(n);
        for (long c : set) {
            if (best == -1 || Math.abs(c - numN) < Math.abs(best - numN) ||
                (Math.abs(c - numN) == Math.abs(best - numN) && c < best)) {
                best = c;
            }
        }
        return String.valueOf(best);
    }
}

C++:

class Solution {
public:
    string nearestPalindromic(string n) {
        int len = n.size();
        set<long long> s;
        s.insert(pow(10, len - 1) - 1);
        s.insert(pow(10, len) + 1);
        long long prefix = stoll(n.substr(0, (len + 1) / 2));
        for (long long i : {-1, 0, 1}) {
            string p = to_string(prefix + i);
            string r = p;
            reverse(r.begin(), r.end());
            s.insert(stoll(p + r.substr(len % 2)));
        }
        s.erase(stoll(n));
        long long best = -1, numN = stoll(n);
        for (long long c : s) {
            if (best == -1 || abs(c - numN) < abs(best - numN) ||
                (abs(c - numN) == abs(best - numN) && c < best)) {
                best = c;
            }
        }
        return to_string(best);
    }
};

Go:

import (
    "math"
    "strconv"
)

func nearestPalindromic(n string) string {
    len_n := len(n)
    candidates := make(map[int64]bool)
    candidates[int64(math.Pow(10, float64(len_n-1)))-1] = true
    candidates[int64(math.Pow(10, float64(len_n)))+1] = true

    prefix, _ := strconv.ParseInt(n[:(len_n+1)/2], 10, 64)
    for i := int64(-1); i <= 1; i++ {
        p := strconv.FormatInt(prefix+i, 10)
        r := reverseStr(p)
        var res string
        if len_n%2 == 0 {
            res = p + r
        } else {
            res = p + r[1:]
        }
        val, _ := strconv.ParseInt(res, 10, 64)
        candidates[val] = true
    }

    numN, _ := strconv.ParseInt(n, 10, 64)
    delete(candidates, numN)

    best := int64(-1)
    for c := range candidates {
        if best == -1 || absStr(c-numN) < absStr(best-numN) ||
            (absStr(c-numN) == absStr(best-numN) && c < best) {
            best = c
        }
    }
    return strconv.FormatInt(best, 10)
}

func reverseStr(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

func absStr(a int64) int64 {
    if a < 0 { return -a }
    return a
}

Ruby:

def nearest_palindromic(n)
  len = n.length
  candidates = Set.new
  candidates.add((10**(len - 1) - 1).to_s)
  candidates.add((10**len + 1).to_s)

  prefix = n[0..(len + 1) / 2 - 1].to_i
  [-1, 0, 1].each do |i|
    p = (prefix + i).to_s
    res = p + p.reverse[len % 2..-1]
    candidates.add(res)
  end

  candidates.delete(n)
  num_n = n.to_i
  best = nil
  candidates.each do |c|
    c_i = c.to_i
    if best.nil? || (c_i - num_n).abs < (best.to_i - num_n).abs ||
       ((c_i - num_n).abs == (best.to_i - num_n).abs && c_i < best.to_i)
      best = c
    end
  end
  best
end

Time Complexity:

O(len)

| Space Complexity:

O(len)

17. Reaching Points

Brief: Given start points (sx, sy) and target points (tx, ty), return true if you can reach target by repeatedly applying (x, y) -> (x+y, y) or (x, x+y).
Why this pattern?: Advanced GCD-like backward simulation.
Key Insight: Working backwards from (tx, ty) is deterministic. Since x, y > 0, only one of tx > ty or ty > tx can be true for the previous step. Use modulo to skip many subtraction steps, similar to the Euclidean algorithm.

Visual:

  graph TD
    Target[tx, ty] --> Check{tx > ty?}
    Check -->|Yes| ModX[tx = tx % ty]
    Check -->|No| ModY[ty = ty % tx]
    ModX & ModY --> Loop[Repeat until tx=sx or ty=sy]

Code Solution:

JavaScript:

function reachingPoints(sx, sy, tx, ty) {
    while (tx >= sx && ty >= sy) {
        if (tx === ty) break;
        if (tx > ty) {
            if (ty > sy) tx %= ty;
            else return (tx - sx) % ty === 0;
        } else {
            if (tx > sx) ty %= tx;
            else return (ty - sy) % tx === 0;
        }
    }
    return tx === sx && ty === sy;
}

Python:

def reachingPoints(sx: int, sy: int, tx: int, ty: int) -> bool:
    while tx >= sx and ty >= sy:
        if tx == ty:
            break
        if tx > ty:
            if ty > sy:
                tx %= ty
            else:
                return (tx - sx) % ty == 0
        else:
            if tx > sx:
                ty %= tx
            else:
                return (ty - sy) % tx == 0
    return tx == sx and ty == sy

Java:

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (tx == ty) break;
            if (tx > ty) {
                if (ty > sy) tx %= ty;
                else return (tx - sx) % ty == 0;
            } else {
                if (tx > sx) ty %= tx;
                else return (ty - sy) % tx == 0;
            }
        }
        return tx == sx && ty == sy;
    }
}

C++:

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (tx == ty) break;
            if (tx > ty) {
                if (ty > sy) tx %= ty;
                else return (tx - sx) % ty == 0;
            } else {
                if (tx > sx) ty %= tx;
                else return (ty - sy) % tx == 0;
            }
        }
        return tx == sx && ty == sy;
    }
};

Go:

func reachingPoints(sx int, sy int, tx int, ty int) bool {
    for tx >= sx && ty >= sy {
        if tx == ty {
            break
        }
        if tx > ty {
            if ty > sy {
                tx %= ty
            } else {
                return (tx-sx)%ty == 0
            }
        } else {
            if tx > sx {
                ty %= tx
            } else {
                return (ty-sy)%tx == 0
            }
        }
    }
    return tx == sx && ty == sy
}

Ruby:

def reaching_points(sx, sy, tx, ty)
  while tx >= sx && ty >= sy
    break if tx == ty
    if tx > ty
      if ty > sy
        tx %= ty
      else
        return (tx - sx) % ty == 0
      end
    else
      if tx > sx
        ty %= tx
      else
        return (ty - sy) % tx == 0
      end
    end
  end
  tx == sx && ty == sy
end

Time Complexity:

O(log(max(tx, ty)))

| Space Complexity:

O(1)

18. Largest Component Size by Common Factor

Brief: Return the size of the largest connected component where nodes have an edge if they share a common factor > 1.
Why this pattern?: Union-Find combined with Prime Factorization.
Key Insight: Instead of checking edges between all pairs (N²), union each number with its prime factors. Numbers sharing a prime factor will end up in the same component.

Visual:

  graph TD
    N1[20] --> P2[2]
    N1 --> P5[5]
    N2[15] --> P3[3]
    N2 --> P5
    P5 --> Connect[20 and 15 in same component via 5]

Code Solution:

JavaScript:

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.size = new Array(n).fill(1);
    }
    find(i) {
        if (this.parent[i] === i) return i;
        return this.parent[i] = this.find(this.parent[i]);
    }
    union(i, j) {
        let rootI = this.find(i);
        let rootJ = this.find(j);
        if (rootI !== rootJ) {
            this.parent[rootI] = rootJ;
            this.size[rootJ] += this.size[rootI];
            return true;
        }
        return false;
    }
}

function largestComponentSize(nums) {
    const maxNum = Math.max(...nums);
    const uf = new UnionFind(maxNum + 1);
    for (let num of nums) {
        for (let f = 2; f * f <= num; f++) {
            if (num % f === 0) {
                uf.union(num, f);
                uf.union(num, num / f);
            }
        }
    }
    const counts = new Map();
    let max = 0;
    for (let num of nums) {
        let root = uf.find(num);
        counts.set(root, (counts.get(root) || 0) + 1);
        max = Math.max(max, counts.get(root));
    }
    return max;
}

Python:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
    def union(self, i, j):
        root_i, root_j = self.find(i), self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j

def largestComponentSize(nums: List[int]) -> int:
    uf = UnionFind(max(nums) + 1)
    for num in nums:
        for f in range(2, int(num**0.5) + 1):
            if num % f == 0:
                uf.union(num, f)
                uf.union(num, num // f)

    counts = collections.Counter(uf.find(num) for num in nums)
    return max(counts.values())

Java:

class Solution {
    class UF {
        int[] parent;
        UF(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) parent[rootI] = rootJ;
        }
    }

    public int largestComponentSize(int[] nums) {
        int max = 0;
        for (int num : nums) max = Math.max(max, num);
        UF uf = new UF(max + 1);
        for (int num : nums) {
            for (int f = 2; f * f <= num; f++) {
                if (num % f == 0) {
                    uf.union(num, f);
                    uf.union(num, num / f);
                }
            }
        }
        Map<Integer, Integer> counts = new HashMap<>();
        int res = 0;
        for (int num : nums) {
            int root = uf.find(num);
            counts.put(root, counts.getOrDefault(root, 0) + 1);
            res = Math.max(res, counts.get(root));
        }
        return res;
    }
}

C++:

class Solution {
    struct UF {
        vector<int> parent;
        UF(int n) {
            parent.resize(n);
            iota(parent.begin(), parent.end(), 0);
        }
        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        void unite(int i, int j) {
            int rI = find(i), rJ = find(j);
            if (rI != rJ) parent[rI] = rJ;
        }
    };
public:
    int largestComponentSize(vector<int>& nums) {
        int max_val = *max_element(nums.begin(), nums.end());
        UF uf(max_val + 1);
        for (int n : nums) {
            for (int f = 2; f * f <= n; f++) {
                if (n % f == 0) {
                    uf.unite(n, f);
                    uf.unite(n, n / f);
                }
            }
        }
        unordered_map<int, int> counts;
        int res = 0;
        for (int n : nums) {
            res = max(res, ++counts[uf.find(n)]);
        }
        return res;
    }
};

Go:

func largestComponentSize(nums []int) int {
    maxVal := 0
    for _, n := range nums {
        if n > maxVal {
            maxVal = n
        }
    }
    parent := make([]int, maxVal+1)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(i int) int {
        if parent[i] == i {
            return i
        }
        parent[i] = find(parent[i])
        return parent[i]
    }
    union := func(i, j int) {
        rootI, rootJ := find(i), find(j)
        if rootI != rootJ {
            parent[rootI] = rootJ
        }
    }

    for _, n := range nums {
        for f := 2; f*f <= n; f++ {
            if n%f == 0 {
                union(n, f)
                union(n, n/f)
            }
        }
    }

    counts := make(map[int]int)
    maxCount := 0
    for _, n := range nums {
        root := find(n)
        counts[root]++
        if counts[root] > maxCount {
            maxCount = counts[root]
        }
    }
    return maxCount
}

Ruby:

class UnionFind
  def initialize(n)
    @parent = (0...n).to_a
  end
  def find(i)
    return i if @parent[i] == i
    @parent[i] = find(@parent[i])
  end
  def union(i, j)
    root_i = find(i)
    root_j = find(j)
    @parent[root_i] = root_j if root_i != root_j
  end
end

def largest_component_size(nums)
  uf = UnionFind.new(nums.max + 1)
  nums.each do |num|
    (2..Math.sqrt(num)).each do |f|
      if num % f == 0
        uf.union(num, f)
        uf.union(num, num / f)
      end
    end
  end
  counts = Hash.new(0)
  nums.map { |n| uf.find(n) }.each { |root| counts[root] += 1 }
  counts.values.max || 0
end

Time Complexity:

O(N * sqrt(M))

where M is max(nums) | Space Complexity:

O(M)

Recommended Study Order

Start with the Basics: Problems 1 (Reverse Integer) and 2 (Palindrome Number) help you master basic digit manipulation.
Arithmetic & Conversion: Move to Problem 3 (Plus One), 4 (Column Number), and 9 (Column Title) to understand how numbers are represented in different bases and arrays.
Core Algorithms: Practice Problem 11 (Pow(x, n)) and 14 (Water Jug) to apply the templates for Fast Exponentiation and GCD.
Mathematical Insight: Solve Problem 12 (Trailing Zeroes) and 13 (Bulb Switcher) to develop the “Aha!” moments needed for purely mathematical problems.
Challenge Yourself: Finish with Problem 16 (Closest Palindrome) and 17 (Reaching Points) to test your ability to handle complex edge cases and large numbers.

Practice Strategy

1. Master the Core Formulas

Mathematical patterns often rely on foundational number theory. Ensure you are comfortable with:

GCD/LCM: The Euclidean algorithm is the bedrock of many math problems.
Prime Factorization: Know how to find divisors in $O(\sqrt{n})$ time.
Modulo Arithmetic: Understand how to handle overflow using $(a + b) \pmod m$.

2. Recognize Hidden Math

Many problems that look like “Array” or “Graph” problems have an underlying mathematical Shortcut. When you see constraints that are too large for BFS/DFS or sorting, ask:

Is there a closed-form formula?
Can I represent this as a base conversion?
Does the state repeat in a predictable cycle?

3. Handle Precision and Overflow

Integer Overflow: Always check if your intermediate products exceed the 32-bit integer limit. Use BigInt or 64-bit integers (long long in C++) where necessary.
Floating Point: Avoid using floating point for exact comparisons. Use a small epsilon $\epsilon = 10^{-9}$ if you must.

Common Patterns Summary

BigInt Operations → String manipulation or array of digits.
Prime Factorization → Sieve of Eratosthenes or trial division up to $\sqrt{n}$.
GCD Applications → Bézout’s Identity and reachability problems.
Base Conversion → Repeated modulo and division.

Ready for more? Check out the Code Templates or return to the Concept Guide.

Interview Tip: When an interviewer gives you a problem involving large integers, don’t just reach for a BigInt library. Explain the mathematical properties you can use to reduce the problem size first!