Find the Sum of Encrypted Integers - Solution & Explanation
Problem Statement
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] <= 1000
Approach Overview
Problem 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 1: Approach 1: Iterative Transformation
This approach involves iterating through the list of numbers, and for each number, finding the largest digit. We replace every digit of the number with this largest digit to form the encrypted number. The sum of these encrypted numbers is then computed.
This C program defines an encrypt function that finds the largest digit of a given number and replaces all digits with this maximum digit. In sumOfEncryptedElements, we iterate over each number, encrypt it, and compute the sum of all encrypted numbers.
Complexity
Time Complexity: O(n * m), where n is the number of elements in the array and m is the number of digits in the largest number.
Space Complexity: O(1), as no additional data structures are used outside of function call stack space.
Approach 2: Approach 2: Precalculate Maximum Digit and Rebuild
This approach involves precalculating the maximum digit for each number and then constructing the new number using a repetitive process. Though similar to Approach 1, this highlights the preprocessing step distinctly and showcases optimization possibilities in reconstruction.
This solution separates the maximum digit determination and number reconstruction into two distinct functions, allowing flexibility in optimization and readability of the code logic.
Complexity
Time Complexity: O(n * m) for both determining the max digit and reconstructing the number. It does not provide an asymptotic improvement over Approach 1.
Space Complexity: O(1).
Approach 3: Simulation
We directly simulate the encryption process by defining a function encrypt(x), which replaces each digit in an integer x with the maximum digit in x. The implementation of the function is as follows:
We can obtain each digit of x by continuously taking the modulus and integer division of x by 10, and find the maximum digit, denoted as mx. During the loop, we can also use a variable p to record the base number of mx, i.e., p = 1, 11, 111, cdots. Finally, return mx times p.
The time complexity is O(n times log M), where n is the length of the array, and M is the maximum value in the array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Transformation | Time Complexity: O(n * m), where n is the number of elements in the array and m is the number of digits in the largest number. |
| Approach 2: Precalculate Maximum Digit and Rebuild | Time Complexity: O(n * m) for both determining the max digit and reconstructing the number. It does not provide an asymptotic improvement over Approach 1. |
| Simulation | — |
Detailed Complexity Analysis
| 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. |
Video Solution
100262. Find the Sum of Encrypted Integers | Leetcode | Biweekly Contest 126 | Sol Code In Comment. • Optimization • 703 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Sum of Encrypted Integers easy or hard?
Find the Sum of Encrypted Integers Python/Java solution
How to solve Find the Sum of Encrypted Integers in O(n)?
What is the best approach for Find the Sum of Encrypted Integers?
Is Find the Sum of Encrypted Integers asked at Google/Amazon/Meta?
What data structure is used in Find the Sum of Encrypted Integers?
What is the time complexity of Find the Sum of Encrypted Integers?
Ready to solve this problem?
Practice Find the Sum of Encrypted Integers with our built-in code editor and test cases.
Practice on FleetCode