Greatest Common Divisor¶
Table of Contents¶
- 1979. Find Greatest Common Divisor of Array (Easy)
- 2807. Insert Greatest Common Divisors in Linked List (Medium)
- 914. X of a Kind in a Deck of Cards (Easy)
- 1071. Greatest Common Divisor of Strings (Easy)
- 2344. Minimum Deletions to Make Array Divisible (Hard)
- 365. Water and Jug Problem (Medium)
- 858. Mirror Reflection (Medium)
- 2654. Minimum Number of Operations to Make All Array Elements Equal to 1 (Medium)
- 1250. Check If It Is a Good Array (Hard)
- 149. Max Points on a Line (Hard)
- 2607. Make K-Subarray Sums Equal (Medium)
- 2447. Number of Subarrays With GCD Equal to K (Medium)
- 2543. Check if Point Is Reachable (Hard)
- 2183. Count Array Pairs Divisible by K (Hard)
- 3312. Sorted GCD Pair Queries (Hard)
- 1819. Number of Different Subsequences GCDs (Hard)
- 2436. Minimum Split Into Subarrays With GCD Greater Than One (Medium) 👑
- 2464. Minimum Subarrays in a Valid Split (Medium) 👑
- 2941. Maximum GCD-Sum of a Subarray (Hard) 👑
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
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¶
-
Tags: Array, Hash Table, Math, Binary Search, Combinatorics, Counting, Number Theory, Prefix Sum