algoadvance

You are given two arrays of integers nums1 and nums2. Each array represents a collection of digits (from 0 to 9). Your task is to find the smallest possible number that can be formed using at least one digit from each array.

Clarifying Questions

1. Can the arrays contain duplicate digits?
   • Yes, the arrays can have duplicate digits.
2. What is the size range for the arrays?
   • The size of the arrays can vary but will generally fit within typical programming constraints, suitable for competitive programming problems.
3. Is the number expected to be in integer form or string form?
   • The result should be an integer.

Strategy

1. Check for Common Digits:
   • If there are common digits between the two arrays, the smallest common digit will be our answer since it will be the smallest single-digit number possible that is present in both arrays.
2. Form Two-Digit Numbers:
   • If no common digits exist, generate the smallest possible two-digit number using one digit from each array. This involves:
     • Finding the minimum digit in nums1.
     • Finding the minimum digit in nums2.
     • Forming the smallest two-digit number by considering the two possible combinations (e.g., if min1 is from nums1 and min2 is from nums2, the two numbers are min1*10 + min2 and min2*10 + min1).

Code

def form_smallest_number(nums1, nums2):
    # Convert arrays to sets to quickly find the intersection
    set_nums1 = set(nums1)
    set_nums2 = set(nums2)
    
    # Find the intersection of both sets
    common_digits = set_nums1 & set_nums2
    
    if common_digits:
        # If there's any common digit, the smallest one is the result
        return min(common_digits)
    
    # Otherwise, find the smallest digits from both arrays
    min1 = min(nums1)
    min2 = min(nums2)
    
    # Form the two smallest possible two-digit numbers
    num1 = min1 * 10 + min2
    num2 = min2 * 10 + min1
    
    # Return the smallest of the two possible numbers
    return min(num1, num2)

# Example usage:
nums1 = [4, 1, 3]
nums2 = [5, 7]
print(form_smallest_number(nums1, nums2))  # Output would be 15

Time Complexity

• Finding the intersection of two sets: (O(n + m)) where (n) is the length of nums1 and (m) is the length of nums2.
• Finding the minimum element in the arrays: (O(n)) for nums1 and (O(m)) for nums2.

Thus, the overall time complexity is (O(n + m)), which is efficient for typical input sizes.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?