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 <= 91 <= 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 × n), and the space complexity is O(1), where m and n are the lengths of the arrays nums1 and nums2.
PythonJavaC++GoTypeScriptRust
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
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.
PythonJavaC++GoTypeScriptRust
class Solution:
def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
s = set(nums1) & set(nums2)
if s:
return min(s)
a, b = min(nums1), min(nums2)
return min(a * 10 + b, b * 10 + a)(code-box)
class Solution {
public int minNumber(int[] nums1, int[] nums2) {
boolean[] s1 = new boolean[10];
boolean[] s2 = new boolean[10];
for (int x : nums1) {
s1[x] = true;
}
for (int x : nums2) {
s2[x] = true;
}
int a = 0, b = 0;
for (int i = 1; i < 10; ++i) {
if (s1[i] && s2[i]) {
return i;
}
if (a == 0 && s1[i]) {
a = i;
}
if (b == 0 && s2[i]) {
b = i;
}
}
return Math.min(a * 10 + b, b * 10 + a);
}
}(code-box)
class Solution {
public:
int minNumber(vector<int>& nums1, vector<int>& nums2) {
bitset<10> s1;
bitset<10> s2;
for (int x : nums1) {
s1[x] = 1;
}
for (int x : nums2) {
s2[x] = 1;
}
int a = 0, b = 0;
for (int i = 1; i < 10; ++i) {
if (s1[i] && s2[i]) {
return i;
}
if (!a && s1[i]) {
a = i;
}
if (!b && s2[i]) {
b = i;
}
}
return min(a * 10 + b, b * 10 + a);
}
};(code-box)
func minNumber(nums1 []int, nums2 []int) int {
s1 := [10]bool{}
s2 := [10]bool{}
for _, x := range nums1 {
s1[x] = true
}
for _, x := range nums2 {
s2[x] = true
}
a, b := 0, 0
for i := 1; i < 10; i++ {
if s1[i] && s2[i] {
return i
}
if a == 0 && s1[i] {
a = i
}
if b == 0 && s2[i] {
b = i
}
}
return min(a*10+b, b*10+a)
}(code-box)
function minNumber(nums1: number[], nums2: number[]): number {
const s1: boolean[] = new Array(10).fill(false);
const s2: boolean[] = new Array(10).fill(false);
for (const x of nums1) {
s1[x] = true;
}
for (const x of nums2) {
s2[x] = true;
}
let a = 0;
let b = 0;
for (let i = 1; i < 10; ++i) {
if (s1[i] && s2[i]) {
return i;
}
if (a === 0 && s1[i]) {
a = i;
}
if (b === 0 && s2[i]) {
b = i;
}
}
return Math.min(a * 10 + b, b * 10 + a);
}(code-box)
use std::collections::HashMap;
impl Solution {
pub fn min_number(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let mut h1: HashMap<i32, bool> = HashMap::new();
for &n in &nums1 {
h1.insert(n, true);
}
let mut h2: HashMap<i32, bool> = HashMap::new();
for &n in &nums2 {
h2.insert(n, true);
}
let mut a = 0;
let mut b = 0;
for i in 1..10 {
if h1.contains_key(&i) && h2.contains_key(&i) {
return i;
}
if a == 0 && h1.contains_key(&i) {
a = i;
}
if b == 0 && h2.contains_key(&i) {
b = i;
}
}
std::cmp::min(a * 10 + b, b * 10 + a)
}
}(code-box)
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 × 10 + b, b × 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.
PythonJavaC++GoTypeScript
class Solution:
def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
mask1 = mask2 = 0
for x in nums1:
mask1 |= 1 << x
for x in nums2:
mask2 |= 1 << x
mask = mask1 & mask2
if mask:
return (mask & -mask).bit_length() - 1
a = (mask1 & -mask1).bit_length() - 1
b = (mask2 & -mask2).bit_length() - 1
return min(a * 10 + b, b * 10 + a)(code-box)
class Solution {
public int minNumber(int[] nums1, int[] nums2) {
int mask1 = 0, mask2 = 0;
for (int x : nums1) {
mask1 |= 1 << x;
}
for (int x : nums2) {
mask2 |= 1 << x;
}
int mask = mask1 & mask2;
if (mask != 0) {
return Integer.numberOfTrailingZeros(mask);
}
int a = Integer.numberOfTrailingZeros(mask1);
int b = Integer.numberOfTrailingZeros(mask2);
return Math.min(a * 10 + b, b * 10 + a);
}
}(code-box)
class Solution {
public:
int minNumber(vector<int>& nums1, vector<int>& nums2) {
int mask1 = 0, mask2 = 0;
for (int x : nums1) {
mask1 |= 1 << x;
}
for (int x : nums2) {
mask2 |= 1 << x;
}
int mask = mask1 & mask2;
if (mask) {
return __builtin_ctz(mask);
}
int a = __builtin_ctz(mask1);
int b = __builtin_ctz(mask2);
return min(a * 10 + b, b * 10 + a);
}
};(code-box)
func minNumber(nums1 []int, nums2 []int) int {
var mask1, mask2 uint
for _, x := range nums1 {
mask1 |= 1 << x
}
for _, x := range nums2 {
mask2 |= 1 << x
}
if mask := mask1 & mask2; mask != 0 {
return bits.TrailingZeros(mask)
}
a, b := bits.TrailingZeros(mask1), bits.TrailingZeros(mask2)
return min(a*10+b, b*10+a)
}(code-box)
function minNumber(nums1: number[], nums2: number[]): number {
let mask1: number = 0;
let mask2: number = 0;
for (const x of nums1) {
mask1 |= 1 << x;
}
for (const x of nums2) {
mask2 |= 1 << x;
}
const mask = mask1 & mask2;
if (mask !== 0) {
return numberOfTrailingZeros(mask);
}
const a = numberOfTrailingZeros(mask1);
const b = numberOfTrailingZeros(mask2);
return Math.min(a * 10 + b, b * 10 + a);
}
function numberOfTrailingZeros(i: number): number {
let y = 0;
if (i === 0) {
return 32;
}
let n = 31;
y = i << 16;
if (y != 0) {
n = n - 16;
i = y;
}
y = i << 8;
if (y != 0) {
n = n - 8;
i = y;
}
y = i << 4;
if (y != 0) {
n = n - 4;
i = y;
}
y = i << 2;
if (y != 0) {
n = n - 2;
i = y;
}
return n - ((i << 1) >>> 31);
}(code-box)
