Longest Decimal Prefix Shared Across Two Integer Arrays
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Longest Decimal Prefix Shared Across Two Integer Arrays
You are given two arrays `arr1` and `arr2` of positive integers.
A prefix of a positive integer consists of one or more consecutive decimal digits starting at its leftmost digit. For example, `73` is a prefix of `7328`, while `32` is not.
Choose one integer from `arr1` and one from `arr2`. Return the greatest possible length of a prefix shared by the chosen pair. If no pair shares even its first digit, return `0`.
### Examples
**Example 1**
```text
Input: arr1 = [732,9814], arr2 = [7399,9820]
Output: 2
```
The pair `(732,7399)` shares prefix `73`, and `(9814,9820)` shares prefix `98`. Both have length two; neither of these pairs agrees on a third digit. The other cross-array pairs disagree on their first digit.
**Example 2**
```text
Input: arr1 = [1200,5], arr2 = [12,567]
Output: 2
```
The complete number `12` is a prefix of `1200`, giving length two. The pair `(5,567)` shares only one digit. No other pair gives a longer common prefix.
### Constraints
- `1 <= arr1.length, arr2.length <= 5 * 10^4`.
- `1 <= arr1[i], arr2[i] <= 10^8`.
### Clarifying Questions
- Must the same prefix be shared by every element of both arrays? No; maximize over pairs with one element from each array.
- Can a whole shorter number be the common prefix? Yes, as in `12` and `1200`.
- Do common prefixes between two elements of the same array count by themselves? No; a qualifying pair must cross the two arrays.
- Is the prefix value returned? No; return its number of digits.
- Are duplicate values forbidden? No; there is no uniqueness guarantee.
### C++ Interface
```cpp
class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
}
};
```
### Reasoning Checkpoints
- Compare leading decimal digits using a pair drawn from different arrays.
- Allow an entire shorter number as a prefix and return a digit count.
- Cover equal values, absent common prefixes, and the full stated bounds in the correctness and complexity analysis.
```hint Remove trailing digits to enumerate prefixes
Integer division by ten removes the last decimal digit. Store the positive prefixes generated from arr1, then examine the positive prefixes of each arr2 value from longest to shortest.
```
Overview: Find the greatest decimal common-prefix length over pairs drawn from two positive-integer arrays, including complete shorter numbers and duplicate values.