Watch 10 video solutions for Find the Sum of Encrypted Integers, a easy level problem involving Array, Math. This walkthrough by Optimization has 703 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums containing positive integers. We define a function encrypt such that encrypt(x) replaces every digit in x with the largest digit in x. For example, encrypt(523) = 555 and encrypt(213) = 333.
Return the sum of encrypted elements.
Example 1:
Input: nums = [1,2,3]
Output: 6
Explanation: The encrypted elements are [1,2,3]. The sum of encrypted elements is 1 + 2 + 3 == 6.
Example 2:
Input: nums = [10,21,31]
Output: 66
Explanation: The encrypted elements are [11,22,33]. The sum of encrypted elements is 11 + 22 + 33 == 66.
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 1000Problem Overview: You receive an array of integers. Each number must be encrypted by replacing every digit with the maximum digit present in that number. For example, 523 becomes 555 because the largest digit is 5. After encrypting every value, return the total sum of the encrypted numbers.
The task is mostly digit manipulation. For each number, extract digits, determine the maximum digit, rebuild a number consisting only of that digit repeated for the same length, then accumulate the result. The problem relies on basic operations from array iteration and math digit processing.
Approach 1: Iterative Transformation (O(n · d) time, O(1) space)
Iterate through each number in the array and process its digits using modulo and division. During the scan, track two values: the maximum digit seen so far and the number of digits. Once all digits are processed, rebuild the encrypted number by repeating the maximum digit the same number of times (for example, length 3 and max digit 7 becomes 777). Add this value to the running sum. This approach performs digit extraction and reconstruction directly with simple loops, making it easy to implement in any language.
The key insight: the encrypted value depends only on two pieces of information—the maximum digit and the digit count. Every other detail of the original number becomes irrelevant. Since each digit is processed once, the work per number is proportional to its digit count d. Total complexity is O(n · d) with constant extra memory.
Approach 2: Precalculate Maximum Digit and Rebuild (O(n · d) time, O(1) space)
Separate the process into two explicit steps. First, iterate through the digits of the number to compute the maximum digit. Second, iterate again (or use the stored digit length) to construct the encrypted number by repeatedly multiplying the result by 10 and adding the maximum digit. This produces values like 999 or 4444 depending on the original length.
This approach makes the logic clearer: one pass determines the transformation rule (maximum digit), and the second pass performs reconstruction. It is especially useful when writing clean, readable implementations or when adapting the logic for similar digit-replacement problems in math-based questions.
Recommended for interviews: The iterative transformation approach is typically expected. It demonstrates that you can manipulate digits using modulo/division and reason about number reconstruction efficiently. The precalculation variant shows the same insight but with slightly clearer separation of steps. Both run in O(n · d) time and O(1) space, which is optimal for this problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Transformation | O(n · d) | O(1) | Best general solution. Processes digits once per number and rebuilds the encrypted value directly. |
| Precalculate Maximum Digit and Rebuild | O(n · d) | O(1) | Good when separating logic for clarity—first compute max digit, then construct the encrypted number. |