3270. Find the Key of the Numbers

Problem Description

You are given three positive integers, num1, num2, and num3. The goal is to generate a key that is a four-digit number based on these three numbers.

If any of these integers have fewer than four digits, they should be padded with leading zeros to make them four-digit numbers.
The i^th digit of the key is formed by taking the smallest digit among the i^th digits of num1, num2, and num3.

The task is to return the key of the three numbers without any leading zeros, if there are any.

Intuition

The solution involves simulating the process of constructing the key digit by digit. The idea is to look at each place value (unit, ten, hundred, thousand) and determine the smallest digit that can be formed from the corresponding digits of num1, num2, and num3.

Start from the units place (1 as k), and extract the corresponding digit from each of the three numbers by using modulus and integer division.
Compare these digits and take the smallest one as the digit for the current place in the key.
Add this digit to the result (ans) and multiply it by k, which represents the current place value.
Move to the next digit place (e.g., tens, hundreds) by multiplying k by 10.
Repeat this process for four places.

By iterating through the digits and picking the smallest for each place, we can construct the key according to the given rules. Finally, return the assembled number without leading zeros.

Learn more about Math patterns.

Solution Approach

The approach to solve this problem is a straightforward simulation of the digit comparison process described. Here's how the solution is implemented:

Initialization:
- Create a variable ans to store the final key value. Initialize it to zero.
- Initialize a variable k to keep track of the current digit place, starting with the units place (k = 1).
Iterate Through Each Digit Place:
- For each of the four digit places (unit, ten, hundred, thousand):
  - Extract the current digit for each number (num1, num2, num3) at the current place. This is done using the expression number // k % 10.
  - Use the min function to find the smallest digit among the three extracted digits.
  - Add this minimum digit, appropriately multiplied by k, to ans.
  - Multiply k by 10 to move on to the next higher digit place.
Return the Result:
- After processing all four digit places, ans contains the value of the key without leading zeros.
- Return ans.

By using this method, we efficiently construct the desired key by directly comparing the corresponding digits from the three numbers and forming the smallest possible value for each digit position.

class Solution:
    def generateKey(self, num1: int, num2: int, num3: int) -> int:
        ans, k = 0, 1
        for _ in range(4):
            x = min(num1 // k % 10, num2 // k % 10, num3 // k % 10)
            ans += x * k
            k *= 10
        return ans

The straightforward simulation leverages basic arithmetic operations and a loop to efficiently solve the problem without the need for any advanced data structures or algorithms.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example using the provided solution approach to generate a key. Assume the inputs are num1 = 1930, num2 = 2055, and num3 = 3098.

Initialization:
- Set ans to 0. This variable will accumulate the result.
- Initialize k to 1 representing the units place.
Iterate Through Each Digit Place:
- Units Place (k = 1):
  - Extract and compare the units digits: num1 % 10 = 0, num2 % 10 = 5, num3 % 10 = 8.
  - The smallest digit is 0.
  - Update ans: ans += 0 * 1 = 0.
  - Multiply k by 10 to move to the next digit place: k = 10.
- Tens Place (k = 10):
  - Extract and compare the tens digits: 1930 // 10 % 10 = 3, 2055 // 10 % 10 = 5, 3098 // 10 % 10 = 9.
  - The smallest digit is 3.
  - Update ans: ans += 3 * 10 = 30.
  - Multiply k by 10: k = 100.
- Hundreds Place (k = 100):
  - Extract and compare the hundreds digits: 1930 // 100 % 10 = 9, 2055 // 100 % 10 = 0, 3098 // 100 % 10 = 0.
  - The smallest digit is 0.
  - Update ans: ans += 0 * 100 = 30.
  - Multiply k by 10: k = 1000.
- Thousands Place (k = 1000):
  - Extract and compare the thousands digits: 1930 // 1000 % 10 = 1, 2055 // 1000 % 10 = 2, 3098 // 1000 % 10 = 3.
  - The smallest digit is 1.
  - Update ans: ans += 1 * 1000 = 1030.
  - Multiply k by 10 to finalize.
Return the Result:
- The final value of ans is 1030, which serves as the key without any leading zeros.

Using this method, we efficiently generate the key by extracting the smallest digits from each corresponding digit place in the given numbers.

Solution Implementation

1class Solution:
2    def generateKey(self, num1: int, num2: int, num3: int) -> int:
3        # Initialize the answer to zero and the positional factor to one
4        answer, factor = 0, 1
5      
6        # Iterate for each digit position (4 times based on the context)
7        for _ in range(4):
8            # Get the digits at the current position for each number
9            digit1 = (num1 // factor) % 10
10            digit2 = (num2 // factor) % 10
11            digit3 = (num3 // factor) % 10
12          
13            # Find the smallest digit among the three numbers
14            min_digit = min(digit1, digit2, digit3)
15          
16            # Add the smallest digit times the current factor to the answer
17            answer += min_digit * factor
18          
19            # Move to the next digit position (e.g., tens, hundreds)
20            factor *= 10
21      
22        # Return the generated key
23        return answer
24

1class Solution {
2    /**
3     * Generate a key based on the smallest digits at each position from three numbers.
4     * 
5     * @param num1 First number for comparison.
6     * @param num2 Second number for comparison.
7     * @param num3 Third number for comparison.
8     * @return The key generated by selecting the smallest digit from each digit position.
9     */
10    public int generateKey(int num1, int num2, int num3) {
11        int result = 0; // Holds the final generated key
12        int placeValue = 1; // Represents the current digit's place value (units, tens, hundreds, etc.)
13      
14        for (int i = 0; i < 4; ++i) { // Iterate over the first 4 digits
15            // Extract the current digit for each number and find the minimum among them
16            int minDigit = Math.min(
17                Math.min(num1 / placeValue % 10, num2 / placeValue % 10), 
18                num3 / placeValue % 10
19            );
20          
21            // Add the minimum digit for the current place to the result
22            result += minDigit * placeValue;
23          
24            // Move to the next digit position
25            placeValue *= 10;
26        }
27      
28        return result;
29    }
30}
31

1class Solution {
2public:
3    int generateKey(int num1, int num2, int num3) {
4        int ans = 0;  // To store the resulting key
5        int k = 1;    // Multiplier to extract digits from each place (units, tens, hundreds, etc.)
6
7        // Loop to process each of the 4 least significant digits
8        for (int i = 0; i < 4; ++i) {
9            // Extract the digit at the ith position from each number
10            int digit1 = (num1 / k) % 10;
11            int digit2 = (num2 / k) % 10;
12            int digit3 = (num3 / k) % 10;
13
14            // Find the minimum digit among the three
15            int minDigit = std::min({digit1, digit2, digit3});
16
17            // Add the minimum digit to the result at the ith position
18            ans += minDigit * k;
19
20            // Move to the next significant digit
21            k *= 10;
22        }
23
24        return ans;  // Return the generated key
25    }
26};
27

1// Function to generate a key from three numbers based on their digits.
2function generateKey(num1: number, num2: number, num3: number): number {
3    let ans = 0; // Initialize the final answer to 0
4    let k = 1;   // Initialize multiplier to handle digit shifts
5
6    // Loop over four digits (assuming numbers have 4 or more decimal places)
7    for (let i = 0; i < 4; ++i) {
8        // Calculate the current digit in base 10 for each number
9        const digit1 = ((num1 / k) | 0) % 10;
10        const digit2 = ((num2 / k) | 0) % 10;
11        const digit3 = ((num3 / k) | 0) % 10;
12
13        // Determine the smallest digit among the three numbers
14        const minDigit = Math.min(digit1, digit2, digit3);
15
16        // Add the smallest digit to the result with the correct place value
17        ans += minDigit * k;
18
19        // Move to the next digit place
20        k *= 10;
21    }
22
23    // Return the final calculated number
24    return ans;
25}
26

Time and Space Complexity

The time complexity of the code is O(1) because the loop executes a fixed number of iterations (4 times regardless of the input values), and each iteration performs a constant time operation.

The space complexity of the code is O(1) because no additional space grows with the size of the input. The variables ans, k, and x use a constant amount of space.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know