Skip to content

Greatest Common Divisor

Table of Contents

1979. Find Greatest Common Divisor of Array

2807. Insert Greatest Common Divisors in Linked List

914. X of a Kind in a Deck of Cards

1071. Greatest Common Divisor of Strings

2344. Minimum Deletions to Make Array Divisible

365. Water and Jug Problem

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


# GCD
def maxPoints(points: List[List[int]]) -> int:
    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


points = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]
print(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

2464. Minimum Subarrays in a Valid Split

2941. Maximum GCD-Sum of a Subarray

Comments