Katkat
Back

Find largest digit-sharing subset

GoogleSoftware Engineer · Online Assessment
EasySoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates a candidate's ability to reason about digit-based frequency analysis and efficient counting on arrays, testing competencies in combinatorics and algorithmic optimization for grouping elements by shared features.

You are given an array of N integers. Each integer has exactly two decimal digits (i.e., each element is between 10 and 99 inclusive).

You want to choose some of the array elements to form a group. A group is valid if there exists at least one digit (0–9) that appears in every number in the group.

  • For example, numbers 52, 25, and 55 can form a valid group because they all contain digit 5.
  • Numbers 11, 52, and 34 cannot form a valid group, because there is no single digit that appears in all three numbers.

Your task:

  • Determine the maximum possible size of a valid group that can be chosen from the array.
  • If no two numbers share a digit, the answer can be 1 (any single element is trivially a valid group, since the shared digit condition holds vacuously for one element).

Input:

  • An integer N (number of elements in the array).
  • N integers, each between 10 and 99 inclusive.

Output:

  • A single integer: the maximum size of a valid group.

You should design an efficient algorithm that works for large N.