LeetCode 3079 - Find the Sum of Encrypted Integers

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem provides an array of positive integers nums and asks us to compute a sum based on an encryption transformation. The transformation encrypt(x) replaces every digit in x with the largest digit in x. For example, encrypt(523) results in 555 because the largest digit in 523 is 5, and every digit is replaced by 5. Similarly, encrypt(213) results in 333.

The goal is to sum the encrypted numbers. For instance, if nums = [10,21,31], the encrypted numbers are [11,22,33] and the sum is 66. The function should return this sum as an integer.

Constraints indicate that nums contains at most 50 elements and each element is between 1 and 1000. This tells us the array size is small and individual integers are small, which means even a straightforward brute-force approach will run efficiently. Edge cases include single-element arrays, numbers with all identical digits, and numbers with zeros.

Approaches

The brute-force approach involves iterating through each number in nums, converting it to a string to examine its digits, finding the largest digit, and then reconstructing the number by repeating this digit for the length of the original number. Finally, sum all the reconstructed numbers. This is correct but involves string manipulation and repeated conversions. Given the constraints, it is fast enough, but can be simplified by working directly with integers.

The key insight for an optimal approach is that each number can be processed independently. By converting the number to a string, finding the maximum digit, and constructing the encrypted number using integer arithmetic or string multiplication, we can efficiently generate the sum. Because the array is small, this approach is essentially optimal in practice.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(1)	Iterate each number, find max digit, reconstruct number, sum
Optimal	O(n * k)	O(1)	Same as brute force; optimal given constraints

Here, n is the length of nums and k is the number of digits in each number (up to 4 since nums[i] ≤ 1000).

Algorithm Walkthrough

Initialize a variable total_sum to 0. This will accumulate the sum of encrypted integers.
Iterate through each number num in the input array nums.
Convert the number to a string to access individual digits.
Determine the largest digit max_digit in the number by using Python's built-in max function on the string of digits.
Compute the encrypted number by repeating max_digit for the same number of digits as the original number. Convert this string back to an integer.
Add the encrypted number to total_sum.
After processing all numbers, return total_sum.

Why it works: The algorithm preserves the exact rule of encryption for each number independently. By processing numbers individually and summing their encrypted forms, the invariant that the sum contains only fully encrypted numbers holds, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def sumOfEncryptedInt(self, nums: List[int]) -> int:
        total_sum = 0
        for num in nums:
            digits = str(num)
            max_digit = max(digits)
            encrypted_num = int(max_digit * len(digits))
            total_sum += encrypted_num
        return total_sum

The Python implementation follows the algorithm directly. We iterate through nums, find the largest digit for each number, repeat it to construct the encrypted number, and accumulate the sum. Conversion between integers and strings is straightforward and efficient for the problem's constraints.

Go Solution

import "strconv"

func sumOfEncryptedInt(nums []int) int {
    totalSum := 0
    for _, num := range nums {
        strNum := strconv.Itoa(num)
        maxDigit := '0'
        for _, ch := range strNum {
            if ch > maxDigit {
                maxDigit = ch
            }
        }
        encryptedNum := 0
        for i := 0; i < len(strNum); i++ {
            encryptedNum = encryptedNum*10 + int(maxDigit-'0')
        }
        totalSum += encryptedNum
    }
    return totalSum
}

In Go, we convert integers to strings using strconv.Itoa to access digits, find the maximum character, and reconstruct the encrypted integer using integer arithmetic. We avoid converting the repeated string back to an integer to handle small integers directly.

Worked Examples

Example 1: nums = [1,2,3]

num	digits	max_digit	encrypted_num	total_sum
1	"1"	"1"	1	1
2	"2"	"2"	2	3
3	"3"	"3"	3	6

Output: 6

Example 2: nums = [10,21,31]

num	digits	max_digit	encrypted_num	total_sum
10	"10"	"1"	11	11
21	"21"	"2"	22	33
31	"31"	"3"	33	66

Output: 66

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * k)	Iterate each number (n) and find max digit among k digits
Space	O(1)	Only variables for sum and temporary digits are used

Since n ≤ 50 and k ≤ 4, this algorithm is very efficient in practice.

Test Cases

# Provided examples
assert Solution().sumOfEncryptedInt([1,2,3]) == 6  # single digits
assert Solution().sumOfEncryptedInt([10,21,31]) == 66  # multiple digits

# Edge cases
assert Solution().sumOfEncryptedInt([9]) == 9  # single-element, single-digit
assert Solution().sumOfEncryptedInt([1000]) == 1111  # largest number, repeated digit
assert Solution().sumOfEncryptedInt([111,222,333]) == 666  # repeated digits
assert Solution().sumOfEncryptedInt([91,82,73]) == 222  # decreasing digits
assert Solution().sumOfEncryptedInt([5,15,105,1005]) == 5+11+111+1111  # mixed digits

Test	Why
[1,2,3]	Single-digit numbers
[10,21,31]	Multi-digit numbers with different largest digits
[9]	Single-element array
[1000]	Maximum value, zeros present
[111,222,333]	All digits identical
[91,82,73]	Largest digit not in first position
[5,15,105,1005]	Mixed single and multi-digit numbers

Edge Cases

One important edge case is numbers with a zero in them, e.g., 10. Without careful handling, zero could mistakenly become part of the maximum digit. The implementation correctly identifies the largest digit and constructs the number by repeating it.

Another edge case is numbers with all identical digits, e.g., 222. In this case, the largest digit is the digit itself. Our method handles this without special treatment because repeating the largest digit results in the same number.

A third edge case is the largest possible number in the input, 1000. The function must correctly handle multi-digit numbers with leading digits smaller than the repeated maximum. Our string-based approach finds the correct maximum digit and repeats it, producing 1111 as expected.

These edge cases ensure robustness across the entire input range defined in the constraints.