Skip to content

Greatest Common Divisor

Table of Contents

1979. Find Greatest Common Divisor of Array

from typing import List


class Solution:
    def findGCD(self, nums: List[int]) -> int:
        def gcd(x, y):
            if y == 0:
                return x
            return gcd(y, x % y)

        return gcd(max(nums), min(nums))

2807. Insert Greatest Common Divisors in Linked List

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertGreatestCommonDivisors(
        self, head: Optional[ListNode]
    ) -> Optional[ListNode]:
        def gcd(x, y):
            if y == 0:
                return x
            return gcd(y, x % y)

        dummy = head
        cur = dummy

        while cur.next:
            v1, v2 = cur.val, cur.next.val
            new = ListNode(val=gcd(max(v1, v2), min(v1, v2)))
            new.next = cur.next
            cur.next = new
            cur = cur.next.next

        return dummy

914. X of a Kind in a Deck of Cards

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Math, Counting, Number Theory

from collections import Counter
from functools import reduce
from math import gcd
from typing import List


class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        if len(deck) < 2:
            return False
        return reduce(gcd, Counter(deck).values()) >= 2

1071. Greatest Common Divisor of Strings

2344. Minimum Deletions to Make Array Divisible

  • LeetCode | 力扣

  • Tags: Array, Math, Sorting, Heap Priority Queue, Number Theory

365. Water and Jug Problem

  • LeetCode | 力扣

  • Tags: Math, Depth First Search, Breadth First Search

from collections import deque


class canMeasureWater:
    def bfs(self, x: int, y: int, target: int) -> bool:
        if target == 0:
            return False
        if x + y < target:
            return False

        visited = set()
        q = deque([(0, 0)])
        visited.add((0, 0))

        while q:
            j1, j2 = q.popleft()
            if j1 + j2 == target or j1 == target or j2 == target:
                return True

            next_states = [
                (x, j2),  # fill jug 1
                (j1, y),  # fill jug 2
                (0, j2),  # empty jug 1
                (j1, 0),  # empty jug 2
                # pour from jug 1 to jug 2
                (j1 - min(j1, y - j2), j2 + min(j1, y - j2)),
                # pour from jug 2 to jug 1
                (j1 + min(j2, x - j1), j2 - min(j2, x - j1)),
            ]

            for state in next_states:
                if state not in visited:
                    q.append(state)
                    visited.add(state)

        return False

858. Mirror Reflection

2654. Minimum Number of Operations to Make All Array Elements Equal to 1

1250. Check If It Is a Good Array

149. Max Points on a Line

from collections import defaultdict
from typing import List


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        # edge case
        n = len(points)
        if n <= 2:
            return n

        res = 0

        for i in range(n - 1):
            x1, y1 = points[i]
            cnt = defaultdict(int)

            for j in range(i + 1, n):
                x2, y2 = points[j]
                g = "inf" if x1 == x2 else (y2 - y1) / (x2 - x1)
                cnt[g] += 1

            res = max(res, 1 + max(cnt.values()))

        return res


if __name__ == "__main__":
    sol = Solution()
    points = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]
    assert sol.maxPoints(points) == 4

2607. Make K-Subarray Sums Equal

2447. Number of Subarrays With GCD Equal to K

2543. Check if Point Is Reachable

2183. Count Array Pairs Divisible by K

3312. Sorted GCD Pair Queries

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Math, Binary Search, Combinatorics, Counting, Number Theory, Prefix Sum

1819. Number of Different Subsequences GCDs

2436. Minimum Split Into Subarrays With GCD Greater Than One 👑

  • LeetCode | 力扣

  • Tags: Array, Math, Dynamic Programming, Greedy, Number Theory

2464. Minimum Subarrays in a Valid Split 👑

  • LeetCode | 力扣

  • Tags: Array, Math, Dynamic Programming, Number Theory

2941. Maximum GCD-Sum of a Subarray 👑