LeetCode 3270 - Find the Key of the Numbers

LeetCode Problem 3270

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem gives us three positive integers, num1, num2, and num3. We must construct a new number called the key using the digits of these three numbers.

The important detail is that every number must first be treated as a four digit number. If a number has fewer than four digits, we pad it with leading zeros. For example:

• 1 becomes "0001"
• 25 becomes "0025"
• 987 becomes "0987"

Once all three numbers are represented as four digit strings, we examine each digit position independently.

For every position from left to right:

• Look at the corresponding digit from all three numbers
• Take the smallest digit
• Place that digit into the resulting key

Finally, we return the resulting number as an integer, which means any leading zeros naturally disappear.

For example:

• num1 = 1 becomes "0001"
• num2 = 10 becomes "0010"
• num3 = 1000 becomes "1000"

Comparing each position:

Position	Digits	Minimum
1	0, 0, 1	0
2	0, 0, 0	0
3	0, 1, 0	0
4	1, 0, 0	0

The resulting key is "0000", which as an integer is 0.

The constraints are very small:

• 1 <= num1, num2, num3 <= 9999

This tells us:

• Every number has at most four digits
• Performance is not a concern
• Even a straightforward solution will be fast enough

However, we still want a clean and reliable implementation.

There are several important edge cases:

• Numbers with different digit lengths, because leading zero padding matters
• Cases where the resulting key begins with zeros
• Cases where all digits become zero
• Numbers already containing four digits
• Inputs where one number is much smaller than the others

The problem guarantees all inputs are positive integers, so we never need to handle negative numbers or invalid input.

Approaches

Brute Force Approach

A brute force solution could generate all padded versions of the numbers as strings, then compare each digit position manually.

The process would be:

1. Convert each number to a four character string using leading zeros
2. Iterate through all four positions
3. Extract the digit from each number
4. Compute the minimum
5. Append it to the answer string
6. Convert the final string back into an integer

This works because the problem definition directly describes digit by digit comparison.

Since there are always exactly four digits, the runtime is effectively constant.

Optimal Approach

The optimal solution follows exactly the same logic, because the problem size is fixed and tiny. There is no need for advanced optimization.

The key observation is that each digit position is completely independent. We do not need to consider combinations or permutations. For each position, we simply take the minimum digit among the three numbers.

Using zero padded strings makes the implementation simple and avoids complicated arithmetic.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Compare digits position by position using padded strings
Optimal	O(1)	O(1)	Same logic, simplified and clean implementation

Algorithm Walkthrough

1. Convert all three numbers into four digit strings using leading zero padding.

This step ensures every number has exactly four characters, making digit comparison straightforward. For example, 7 becomes "0007". 2. Initialize an empty list or string builder for the result.

We will construct the key one digit at a time. 3. Iterate through the four digit positions from left to right.

For each index:

• Extract the corresponding digit from all three strings
• Convert them into integers if necessary
• Compute the minimum digit

4. Append the minimum digit to the result.

This directly follows the problem definition. 5. After processing all four positions, join the digits into a string.

At this point we have the complete four digit key representation. 6. Convert the resulting string into an integer.

This automatically removes leading zeros. For example:

• "0001" becomes 1
• "0000" becomes 0

Why it works

The algorithm works because the problem defines the key independently for each digit position. By padding all numbers to four digits first, every position aligns correctly. Taking the minimum digit at each position exactly matches the required construction rule, so the produced number is guaranteed to be correct. The problem is asking us to find a “key” for three positive integers, num1, num2, and num3, where the key is a four-digit number derived from the smallest digit in each corresponding position across the three numbers. The challenge is that each number may have fewer than four digits, so we first pad them with leading zeros to ensure they all have exactly four digits. Once padded, the key is generated digit by digit by taking the minimum of the corresponding digits from each number. The final result should be returned as an integer without leading zeros.

The input numbers are guaranteed to be positive integers between 1 and 9999, which ensures no negative numbers or zeros. This constraint also makes it clear that after padding, each number will be represented as a string of length four. Edge cases we need to be careful about include numbers that are very small (like 1) or numbers that are already four digits (like 9999). The problem guarantees valid input within the specified range, so we do not need to handle invalid inputs.

The key insight is that since each number has at most four digits, the problem can be solved efficiently by working on the numbers digit by digit, using string padding to normalize their lengths.

Approaches

The brute-force approach involves explicitly padding the numbers with leading zeros, converting each number into a string of length four, and then iterating through each digit position to compute the minimum digit. This method works correctly because it directly follows the problem definition, but it is verbose and slightly cumbersome.

The optimal approach leverages the same idea but can be implemented more cleanly and efficiently by combining string padding and a simple loop to compute the minimum digit at each position. Since we only deal with four digits, the approach is effectively constant time. The key insight is recognizing that working with strings of equal length allows us to directly compare digits without complicated arithmetic or data structures.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4) = O(1)	O(1)	Pad numbers to length 4 and iterate over digits, storing results
Optimal	O(4) = O(1)	O(1)	Directly compute the minimum digits on-the-fly while constructing the result

Algorithm Walkthrough

1. Convert each input number (num1, num2, num3) to a string padded with leading zeros to make its length exactly four characters. This ensures we can access the digits at corresponding positions directly.
2. Initialize an empty string key_str to build the key digit by digit.
3. Loop over the four digit positions (0 to 3). For each position:

a. Extract the digit at the current position from each of the three padded strings.

b. Convert the digits to integers and compute the minimum among them.

c. Append this minimum digit to key_str. 4. Convert the final key_str to an integer to remove any leading zeros. 5. Return the resulting integer.

Why it works: By padding all numbers to four digits and taking the minimum digit at each position, we ensure that the constructed key matches the definition in the problem statement. Converting the string to an integer removes any unnecessary leading zeros.

Python Solution

class Solution:
    def generateKey(self, num1: int, num2: int, num3: int) -> int:
        str1 = str(num1).zfill(4)
        str2 = str(num2).zfill(4)
        str3 = str(num3).zfill(4)

        result = []

        for i in range(4):
            smallest_digit = min(str1[i], str2[i], str3[i])
            result.append(smallest_digit)

        return int("".join(result))

The implementation begins by converting each number into a four character string using zfill(4). This guarantees that all numbers align digit by digit.

We then create an empty list called result. Using a list is efficient because repeatedly concatenating strings can be slower in larger problems, although here the size is fixed.

The loop runs exactly four times, once for each digit position. At every step:

• We read the corresponding digit from all three strings
• Compute the smallest digit using min
• Append that digit to the result list

Finally, we join all collected digits into a single string and convert it into an integer. This automatically removes leading zeros. # Step 1: pad numbers to 4 digits s1 = str(num1).zfill(4) s2 = str(num2).zfill(4) s3 = str(num3).zfill(4)

    # Step 2: build the key string
    key_str = ""
    for i in range(4):
        min_digit = min(int(s1[i]), int(s2[i]), int(s3[i]))
        key_str += str(min_digit)
    
    # Step 3: convert to integer to remove leading zeros
    return int(key_str)

The implementation first pads each number to ensure uniform length, allowing for simple digit-by-digit comparison. The loop iterates through each of the four positions, computes the minimum digit, and constructs a string representation of the key. Finally, converting the string to an integer removes leading zeros as required.

## Go Solution

```go
package main

import (
	"strconv"
)

func generateKey(num1 int, num2 int, num3 int) int {
	str1 := fmt.Sprintf("%04d", num1)
	str2 := fmt.Sprintf("%04d", num2)
	str3 := fmt.Sprintf("%04d", num3)

	result := ""

	for i := 0; i < 4; i++ {
		smallest := str1[i]

		if str2[i] < smallest {
			smallest = str2[i]
		}

		if str3[i] < smallest {
			smallest = str3[i]
		}

		result += string(smallest)
	}

	answer, _ := strconv.Atoi(result)
	return answer
}

The Go implementation follows the same logic as the Python version.

One Go specific difference is the use of fmt.Sprintf("%04d", num) to create four digit strings with leading zeros.

Go strings are byte indexed, so str[i] returns a byte. Since digits are ASCII characters, direct comparison works correctly.

We also use strconv.Atoi to convert the final string into an integer.

The complete import section should include both packages:

import (
	"fmt"
	"strconv"
)

Worked Examples

Example 1

Input:

num1 = 1
num2 = 10
num3 = 1000

After padding:

Number	Padded Form
num1	0001
num2	0010
num3	1000

Digit comparison:

Position	Digits	Minimum	Result So Far
0	0, 0, 1	0	0
1	0, 0, 0	0	00
2	0, 1, 0	0	000
3	1, 0, 0	0	0000

Final result:

"0000" -> 0

Example 2

Input:

num1 = 987
num2 = 879
num3 = 798

After padding:

Number	Padded Form
num1	0987
num2	0879
num3	0798

Digit comparison:

Position	Digits	Minimum	Result So Far
0	0, 0, 0	0	0
1	9, 8, 7	7	07
2	8, 7, 9	7	077
3	7, 9, 8	7	0777

Final result:

"0777" -> 777

Example 3

Input:

num1 = 1
num2 = 2
num3 = 3

After padding:

Number	Padded Form
num1	0001
num2	0002
num3	0003

Digit comparison:

Position	Digits	Minimum	Result So Far
0	0, 0, 0	0	0
1	0, 0, 0	0	00
2	0, 0, 0	0	000
3	1, 2, 3	1	0001

Final result:

"0001" -> 1

import "strconv"

func generateKey(num1 int, num2 int, num3 int) int { s1 := strconv.Itoa(num1) s2 := strconv.Itoa(num2) s3 := strconv.Itoa(num3)

// Pad strings to length 4
for len(s1) < 4 {
    s1 = "0" + s1
}
for len(s2) < 4 {
    s2 = "0" + s2
}
for len(s3) < 4 {
    s3 = "0" + s3
}

keyStr := ""
for i := 0; i < 4; i++ {
    d1, _ := strconv.Atoi(string(s1[i]))
    d2, _ := strconv.Atoi(string(s2[i]))
    d3, _ := strconv.Atoi(string(s3[i]))
    minDigit := d1
    if d2 < minDigit {
        minDigit = d2
    }
    if d3 < minDigit {
        minDigit = d3
    }
    keyStr += strconv.Itoa(minDigit)
}

result, _ := strconv.Atoi(keyStr)
return result

}

The Go implementation mirrors the Python version. Strings are padded to four characters, digits are extracted and converted to integers, and the minimum is computed for each position. Concatenation builds the key string, which is finally converted to an integer. Go requires explicit conversion between strings and integers, which is handled via `strconv`.

## Worked Examples

**Example 1: num1 = 1, num2 = 10, num3 = 1000**

| Step | s1 | s2 | s3 | min digit | key_str |
| --- | --- | --- | --- | --- | --- |
| 0 | 0001 | 0010 | 1000 | 0 | "0" |
| 1 | 0001 | 0010 | 1000 | 0 | "00" |
| 2 | 0001 | 0010 | 1000 | 0 | "000" |
| 3 | 0001 | 0010 | 1000 | 0 | "0000" |

Result: 0

**Example 2: num1 = 987, num2 = 879, num3 = 798**

| Step | s1 | s2 | s3 | min digit | key_str |
| --- | --- | --- | --- | --- | --- |
| 0 | 0987 | 0879 | 0798 | 0 | "0" |
| 1 | 0987 | 0879 | 0798 | 7 | "07" |
| 2 | 0987 | 0879 | 0798 | 7 | "077" |
| 3 | 0987 | 0879 | 0798 | 7 | "0777" |

Result: 777

**Example 3: num1 = 1, num2 = 2, num3 = 3**

| Step | s1 | s2 | s3 | min digit | key_str |
| --- | --- | --- | --- | --- | --- |
| 0 | 0001 | 0002 | 0003 | 0 | "0" |
| 1 | 0001 | 0002 | 0003 | 0 | "00" |
| 2 | 0001 | 0002 | 0003 | 0 | "000" |
| 3 | 0001 | 0002 | 0003 | 1 | "0001" |

Result: 1

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(1) | Only four digit positions are processed |
| Space | O(1) | Only a few fixed size strings and variables are used |

The runtime is constant because every input is limited to at most four digits. Regardless of the actual values, the algorithm always performs exactly four iterations. The memory usage is also constant because the padded strings and result are all fixed size.

## Test Cases

```sql
solution = Solution()

# Provided examples
assert solution.generateKey(1, 10, 1000) == 0  # all positions become 0
assert solution.generateKey(987, 879, 798) == 777  # mixed digit comparisons
assert solution.generateKey(1, 2, 3) == 1  # smallest final digit survives

# All numbers already four digits
assert solution.generateKey(1234, 5678, 9012) == 1012  # compare each position

# Identical numbers
assert solution.generateKey(5555, 5555, 5555) == 5555  # result unchanged

# Leading zeros in result
assert solution.generateKey(1000, 2000, 3000) == 1000  # first digit survives

# Minimum digits come from different numbers
assert solution.generateKey(8246, 1357, 2468) == 1246  # each position chooses separately

# Smallest possible inputs
assert solution.generateKey(1, 1, 1) == 1  # minimal valid values

# Largest possible inputs
assert solution.generateKey(9999, 9999, 9999) == 9999  # maximal valid values

# Result becomes zero
assert solution.generateKey(1000, 10, 1) == 0  # every position minimum is 0

Test Case Summary

Test	Why
(1, 10, 1000)	Validates leading zero padding
(987, 879, 798)	Verifies per digit minimum logic
(1, 2, 3)	Ensures leading zeros are removed correctly
(1234, 5678, 9012)	Tests four digit numbers
(5555, 5555, 5555)	Confirms identical inputs work
(1000, 2000, 3000)	Tests leading zeros in output
(8246, 1357, 2468)	Checks independent digit selection
(1, 1, 1)	Boundary case with smallest inputs
(9999, 9999, 9999)	Boundary case with largest inputs
(1000, 10, 1)	Confirms output can become zero

Edge Cases

One important edge case occurs when the result contains only zeros. For example, with inputs (1, 10, 1000), every digit position produces 0. A buggy implementation might accidentally return "0000" as a string instead of the integer 0. Our implementation converts the final string into an integer, which correctly produces 0.

Another important case is when the numbers have different digit lengths. Since the comparison is positional, leading zeros matter. For example, 1 must become "0001" before comparison. Without padding, digits would not align correctly and the answer would be wrong. Using zfill(4) in Python and %04d in Go guarantees proper alignment.

A third edge case happens when the smallest digit at each position comes from different numbers. For example:

8246
1357
2468

The minimum digit for each position may come from a different input number. This means we cannot simply choose the smallest overall number. We must compare each digit independently, which our implementation does correctly. | Time | O(1) | There are only four digits, so iteration is constant time | | Space | O(1) | Only a few fixed-length strings and integers are used |

The complexity is constant because the number of digits is bounded by four, regardless of input values.

Test Cases

# provided examples
assert Solution().generateKey(1, 10, 1000) == 0  # all zeros after padding
assert Solution().generateKey(987, 879, 798) == 777  # mixed digits
assert Solution().generateKey(1, 2, 3) == 1  # single-digit numbers

# boundary values
assert Solution().generateKey(1, 1, 1) == 1  # minimal input
assert Solution().generateKey(9999, 9999, 9999) == 9999  # maximal input
assert Solution().generateKey(1, 9999, 5000) == 0  # smallest and largest numbers

# edge cases
assert Solution().generateKey(1000, 2000, 3000) == 1000  # first digit dominates
assert Solution().generateKey(12, 123, 1234) == 12  # padding with zeros

Test	Why
1, 10, 1000