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$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|