# 2605. Form Smallest Number From Two Digit Arrays

## Description

Given two arrays of unique digits nums1 and nums2, return the smallest number that contains at least one digit from each array.

Example 1:

Input: nums1 = [4,1,3], nums2 = [5,7]
Output: 15
Explanation: The number 15 contains the digit 1 from nums1 and the digit 5 from nums2. It can be proven that 15 is the smallest number we can have.


Example 2:

Input: nums1 = [3,5,2,6], nums2 = [3,1,7]
Output: 3
Explanation: The number 3 contains the digit 3 which exists in both arrays.


Constraints:

• 1 <= nums1.length, nums2.length <= 9
• 1 <= nums1[i], nums2[i] <= 9
• All digits in each array are unique.

## Solutions

Solution 1: Enumeration

We observe that if there are the same numbers in the arrays $nums1$ and $nums2$, then the minimum of the same numbers is the smallest number. Otherwise, we take the number $a$ in the array $nums1$ and the number $b$ in the array $nums2$, and concatenate the two numbers $a$ and $b$ into two numbers, and take the smaller number.

The time complexity is $O(m \times n)$, and the space complexity is $O(1)$, where $m$ and $n$ are the lengths of the arrays $nums1$ and $nums2$.

Solution 2: Hash Table or Array + Enumeration

We can use a hash table or array to record the numbers in the arrays $nums1$ and $nums2$, and then enumerate $1 \sim 9$. If $i$ appears in both arrays, then $i$ is the smallest number. Otherwise, we take the number $a$ in the array $nums1$ and the number $b$ in the array $nums2$, and concatenate the two numbers $a$ and $b$ into two numbers, and take the smaller number.

The time complexity is $(m + n)$, and the space complexity is $O(C)$. Where $m$ and $n$ are the lengths of the arrays $nums1$ and $nums2$ respectively; and $C$ is the range of the numbers in the arrays $nums1$ and $nums2$, and the range in this problem is $C = 10$.

Solution 3: Bit Operation

Since the range of the numbers is $1 \sim 9$, we can use a binary number with a length of $10$ to represent the numbers in the arrays $nums1$ and $nums2$. We use $mask1$ to represent the numbers in the array $nums1$, and use $mask2$ to represent the numbers in the array $nums2$.

If the number $mask$ obtained by performing a bitwise AND operation on $mask1$ and $mask2$ is not equal to $0$, then we extract the position of the last $1$ in the number $mask$, which is the smallest number.

Otherwise, we extract the position of the last $1$ in $mask1$ and $mask2$ respectively, and denote them as $a$ and $b$, respectively. Then the smallest number is $min(a \times 10 + b, b \times 10 + a)$.

The time complexity is $O(m + n)$, and the space complexity is $O(1)$. Where $m$ and $n$ are the lengths of the arrays $nums1$ and $nums2$ respectively.

• class Solution {
public int minNumber(int[] nums1, int[] nums2) {
int ans = 100;
for (int a : nums1) {
for (int b : nums2) {
if (a == b) {
ans = Math.min(ans, a);
} else {
ans = Math.min(ans, Math.min(a * 10 + b, b * 10 + a));
}
}
}
return ans;
}
}

• class Solution {
public:
int minNumber(vector<int>& nums1, vector<int>& nums2) {
int ans = 100;
for (int a : nums1) {
for (int b : nums2) {
if (a == b) {
ans = min(ans, a);
} else {
ans = min({ans, a * 10 + b, b * 10 + a});
}
}
}
return ans;
}
};

• class Solution:
def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
ans = 100
for a in nums1:
for b in nums2:
if a == b:
ans = min(ans, a)
else:
ans = min(ans, 10 * a + b, 10 * b + a)
return ans


• func minNumber(nums1 []int, nums2 []int) int {
ans := 100
for _, a := range nums1 {
for _, b := range nums2 {
if a == b {
ans = min(ans, a)
} else {
ans = min(ans, min(a*10+b, b*10+a))
}
}
}
return ans
}

• function minNumber(nums1: number[], nums2: number[]): number {
let ans = 100;
for (const a of nums1) {
for (const b of nums2) {
if (a === b) {
ans = Math.min(ans, a);
} else {
ans = Math.min(ans, a * 10 + b, b * 10 + a);
}
}
}
return ans;
}


• impl Solution {
pub fn min_number(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let mut ans = 100;

for &a in &nums1 {
for &b in &nums2 {
if a == b {
ans = std::cmp::min(ans, a);
} else {
ans = std::cmp::min(ans, std::cmp::min(a * 10 + b, b * 10 + a));
}
}
}

ans
}
}