Find largest group of two-digit numbers sharing digits

Q: Find largest group of two-digit numbers sharing digits

This question evaluates a candidate's ability to model pairwise relationships and compute connected components in small graphs, testing skills in graph connectivity and grouping based on shared attributes in arrays of two-digit numbers.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an integer array A of length n (1 <= n <= 100). Each element is a two-digit number (e.g., from 10 to 99). Two numbers are considered connected if they share at least one digit in common.

Examples of “share a digit”:

55 and 58 share digit 5
25 and 45 share digit 5
12 and 23 share digit 2
55 and 66 share no digit

A group is any set of numbers that can be connected through this relation transitively (i.e., if a shares a digit with b, and b shares a digit with c, then a, b, c can be in the same group even if a and c don’t share a digit directly).

Task: Return the maximum possible size of a group (i.e., the size of the largest connected component under the “shares a digit” relation).

Output: an integer, the largest group size.

Clarifications:

If A contains duplicate values, treat them as separate elements (they each contribute 1 to the group size).
Sharing can be via either the tens digit or the ones digit.

Find largest group of two-digit numbers sharing digits

Overview

Comments (0)