Find largest subset sharing a common digit
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Take-home Project
You are given an array `nums` of length `N` (1 ≤ N ≤ 100). Every element is a **two-digit integer** between **10 and 99** (inclusive).
Select as many elements as possible such that **all selected numbers share at least one common digit** (a digit from 0 to 9). In other words, there exists a digit `d` such that every selected number contains digit `d` in either its tens or ones place.
Return the **maximum possible size** of such a selection.
Examples:
- Input: `[52, 25, 11, 52, 34, 55]` → Output: `4` (e.g., `{52, 25, 52, 55}` all contain digit `5`)
- Input: `[71, 23, 57, 15]` → Output: `2` (e.g., `{71, 57}` share digit `7`)
- Input: `[11, 33, 55]` → Output: `1` (no digit is shared by two numbers)
- Input: `[90, 90, 90]` → Output: `3` (all share digit `9` or digit `0`)
Constraints:
- `1 ≤ N ≤ 100`
- `10 ≤ nums[i] ≤ 99` and each `nums[i]` is strictly two digits.
Quick Answer: This question evaluates array-processing and grouping skills, focusing on identifying shared-digit membership among two-digit integers and aggregating counts to determine the largest compatible subset.
You are given an array nums of length N, where each element is a two-digit integer from 10 to 99 inclusive.
Choose as many elements as possible so that all chosen elements share at least one common digit. That means there must exist some digit d from 0 to 9 such that every selected number contains d in either its tens place or ones place.
Return the maximum possible number of elements you can choose.
Notes:
- Duplicate numbers count as separate elements.
- A number like 11 contains digit 1, but it should only be counted once for digit 1.
Constraints
- 1 <= N <= 100
- 10 <= nums[i] <= 99
- Each nums[i] is a strictly two-digit integer
Examples
Input: ([52, 25, 11, 52, 34, 55],)
Expected Output: 4
Explanation: Digit 5 appears in 52, 25, 52, and 55, so the largest valid subset has size 4.
Input: ([71, 23, 57, 15],)
Expected Output: 2
Explanation: The best possible size is 2. For example, 71 and 57 share digit 7. Also, 71 and 15 share 1, and 57 and 15 share 5.
Input: ([11, 33, 55],)
Expected Output: 1
Explanation: No digit appears in more than one number, so you can only choose one element.
Input: ([90, 90, 90],)
Expected Output: 3