Find the Key of the Numbers

Easy

#2902Time: O(1) - The operations (string formatting, looping 4 times, parsing) are all constant time because the number of digits is fixed at 4.Space: O(1) - The space required for the padded strings and the `StringBuilder` is constant (4 characters each), not dependent on the magnitude of the input numbers (within the given constraints).

Patterns

Math

Prompt

You are given three positive integers num1, num2, and num3.

The key of num1, num2, and num3 is defined as a four-digit number such that:

Initially, if any number has less than four digits, it is padded with leading zeros.
The i^th digit (1 <= i <= 4) of the key is generated by taking the smallest digit among the i^th digits of num1, num2, and num3.

Return the key of the three numbers without leading zeros (if any).

Example 1:

Input: num1 = 1, num2 = 10, num3 = 1000

Output: 0

Explanation:

On padding, num1 becomes "0001", num2 becomes "0010", and num3 remains "1000".

The 1^st digit of the key is min(0, 0, 1).
The 2^nd digit of the key is min(0, 0, 0).
The 3^rd digit of the key is min(0, 1, 0).
The 4^th digit of the key is min(1, 0, 0).

Hence, the key is "0000", i.e. 0.

Example 2:

Input: num1 = 987, num2 = 879, num3 = 798

Output: 777

Example 3:

Input: num1 = 1, num2 = 2, num3 = 3

Output: 1

Constraints:

1 <= num1, num2, num3 <= 9999

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem description into code. It involves converting the numbers to strings, padding them with leading zeros to ensure a four-digit format, and then iterating through the digits to build the key.

Algorithm

Convert num1, num2, and num3 to strings s1, s2, and s3, padding each with leading zeros to a length of 4.
Initialize an empty StringBuilder called keyString.
Loop from i = 0 to 3:
- Get the characters c1 = s1.charAt(i), c2 = s2.charAt(i), c3 = s3.charAt(i).
- Find the minimum character minChar among c1, c2, and c3.
- Append minChar to keyString.
Convert keyString to a string and then parse it as an integer.
Return the resulting integer.

Walkthrough

The core idea is to leverage string formatting to handle the padding requirement easily. First, we convert each integer num1, num2, and num3 into a four-digit string with leading zeros. For example, in Java, String.format("%04d", num) achieves this. Next, we iterate from the first to the fourth digit (index 0 to 3). In each iteration, we extract the character at the current index from all three strings. We find the minimum of these three characters. Since characters '0' through '9' are ordered sequentially in ASCII, a direct comparison using Math.min() works. The resulting minimum character is appended to a StringBuilder which is used to construct the key string. Finally, after the loop completes, the StringBuilder contains the four-digit key as a string. We convert this string back to an integer using Integer.parseInt(), which automatically handles any leading zeros in the final key (e.g., "0777" becomes 777).

1class Solution {2    public int findKey(int num1, int num2, int num3) {3        // Pad numbers with leading zeros to make them 4-digit strings4        String s1 = String.format("%04d", num1);5        String s2 = String.format("%04d", num2);6        String s3 = String.format("%04d", num3);7 8        StringBuilder keyString = new StringBuilder();9 10        // Iterate through each digit position11        for (int i = 0; i < 4; i++) {12            // Get the i-th digit from each number13            char c1 = s1.charAt(i);14            char c2 = s2.charAt(i);15            char c3 = s3.charAt(i);16 17            // Find the smallest digit (character comparison works)18            char minChar = (char) Math.min(c1, Math.min(c2, c3));19            20            // Append the smallest digit to the key21            keyString.append(minChar);22        }23 24        // Convert the final key string to an integer25        return Integer.parseInt(keyString.toString());26    }27}

Complexity

Time

O(1) - The operations (string formatting, looping 4 times, parsing) are all constant time because the number of digits is fixed at 4.

Space

O(1) - The space required for the padded strings and the `StringBuilder` is constant (4 characters each), not dependent on the magnitude of the input numbers (within the given constraints).

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem's definition.
Code is highly readable and self-documenting.
Handles the zero-padding requirement elegantly using built-in string formatting functions.

Cons

Involves multiple type conversions (int to string, string to int) and string object allocations, which can be less performant than pure arithmetic operations.
Uses more memory due to the creation of intermediate string objects.

This approach avoids string conversions entirely and relies on mathematical operations to extract and compare digits. It iteratively builds the final key number by processing digits from most significant (thousands) to least significant (ones).

Algorithm

Initialize key = 0 and placeValue = 1000.
Loop four times (e.g., while (placeValue > 0)):
- Extract the most significant digit from each number: digit1 = num1 / placeValue, digit2 = num2 / placeValue, digit3 = num3 / placeValue.
- Find the minimum digit: minDigit = min(digit1, digit2, digit3).
- Append minDigit to the key: key = key * 10 + minDigit.
- Update the numbers by removing the most significant digit: num1 = num1 % placeValue, etc.
- Update the place value for the next iteration: placeValue = placeValue / 10.
Return the final key.

Walkthrough

The strategy is to calculate the digits of the key one by one, from left to right, and construct the final integer result progressively. We can iterate four times, representing the four digit positions: thousands, hundreds, tens, and ones. A placeValue variable (starting at 1000 and divided by 10 in each step) helps in extracting the correct digit. In each iteration, we calculate the i-th digit of each number. For a number num and a placeValue (e.g., 1000), the digit is num / placeValue. This works because integer division truncates the result. For example, 987 / 1000 is 0, and 1234 / 1000 is 1, correctly giving the thousands digit. We find the minimum of the three extracted digits and append this minimum digit to our result key by using the formula key = key * 10 + minDigit. To prepare for the next iteration, we must remove the digit we just processed from each number using the modulo operator: num = num % placeValue. After four iterations, the key variable will hold the final integer result.

1class Solution {2    public int findKey(int num1, int num2, int num3) {3        int key = 0;4        int placeValue = 1000;5 6        while (placeValue > 0) {7            // Extract the digit at the current place value8            int digit1 = num1 / placeValue;9            int digit2 = num2 / placeValue;10            int digit3 = num3 / placeValue;11 12            // Find the smallest digit13            int minDigit = Math.min(digit1, Math.min(digit2, digit3));14 15            // Build the key16            key = key * 10 + minDigit;17 18            // Remove the processed digit from each number19            num1 %= placeValue;20            num2 %= placeValue;21            num3 %= placeValue;22            23            // Move to the next smaller place value24            placeValue /= 10;25        }26        27        return key;28    }29}

Complexity

Time

O(1) - The loop runs a fixed 4 times, and all operations inside are constant-time arithmetic operations.

Space

O(1) - Only a fixed number of integer variables are used, regardless of the input values.

Trade-offs

Pros

Highly efficient as it uses only integer arithmetic, avoiding the overhead of string creation and manipulation.
Minimal memory usage, requiring only a few integer variables.

Cons

The logic involving division and modulo to extract and update digits can be less intuitive to write and understand compared to the direct string manipulation approach.
Slightly more prone to off-by-one or logical errors if not implemented carefully (e.g., handling the loop termination and place value updates).

Solutions

Solution

1class Solution {2public3  int generateKey(int num1, int num2, int num3) {4    int ans = 0, k = 1;5    for (int i = 0; i < 4; ++i) {6      int x = Math.min(Math.min(num1 / k % 10, num2 / k % 10), num3 / k % 10);7      ans += x * k;8      k *= 10;9    }10    return ans;11  }12}

1class Solution {2public:3  int generateKey(int num1, int num2, int num3) {4    int ans = 0, k = 1;5    for (int i = 0; i < 4; ++i) {6      int x = min({num1 / k % 10, num2 / k % 10, num3 / k % 10});7      ans += x * k;8      k *= 10;9    }10    return ans;11  }12};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem