Handle cards, islands, Trie, median

Question

LeetCode 914. X of a Kind in a Deck of Cards LeetCode 694. Number of Distinct Islands LeetCode 208. Implement Trie (Prefix Tree) LeetCode 295. Find Median from Data Stream

https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/description/ https://leetcode.com/problems/number-of-distinct-islands/description/ https://leetcode.com/problems/implement-trie-prefix-tree/description/ https://leetcode.com/problems/find-median-from-data-stream/description/

Group Deck by Common Divisor

Given an integer array deck where deck[i] is the value of the i-th card, return true if the deck can be partitioned into one or more groups of size X (X >= 2) such that each group has exactly X cards and all cards in each group have the same value. Otherwise, return false.

Constraints

• 1 <= len(deck) <= 10000
• 0 <= deck[i] <= 10000
• Return a boolean indicating whether such a partition exists
• Time expectation: O(n) where n = len(deck)

Examples

Example 1

Input: deck = [1,2,3,4,4,3,2,1]
Output: true

Explanation: Counts are {1:2,2:2,3:2,4:2}; gcd(2,2,2,2) = 2 >= 2, so partition is possible.

Example 2

Input: deck = [1,1,1,2,2,2,3,3]
Output: false

Explanation: Counts are {1:3,2:3,3:2}; gcd(3,3,2) = 1, so no valid group size X >= 2 exists.

Hints

1. Count the frequency of each distinct card value.
2. A partition into equal-sized same-value groups is possible if and only if the greatest common divisor (gcd) of all frequencies is at least 2.
3. Use a running gcd over frequency counts to short-circuit when it becomes 1.

Approach

Compute the frequency of each value. If the gcd of all frequencies is at least 2, then there exists a group size X equal to that gcd (or a divisor thereof >= 2) such that each count is divisible by X, enabling a partition into groups of equal size with identical values. If the gcd ever reduces to 1, no such X >= 2 exists.

• Time complexity: O(n)
• Space complexity: O(k) where k is the number of distinct card values