Scale Engineer

Find the Sum of Encrypted Integers

Easy
#2735Time: O(N * D), where N is the number of elements in `nums` and D is the maximum number of digits in an element. For each number, we convert it to a string (O(D)), iterate through its digits (O(D)), and build the new number (O(D)).Space: O(D), where D is the maximum number of digits in an element. This is for storing the string representation of the number. Since D is small and bounded by the constraints (max 4 for nums[i] <= 1000), this is effectively O(1) constant space.1 company
Patterns
Math
Data structures
Array
Companies
Larsen Toubro

Prompt

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 <= 50
  • 1 <= nums[i] <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each number in the input array. For each number, it converts it to a string to easily access its digits. It then finds the largest digit and the number of digits. Finally, it constructs the encrypted number by repeating the largest digit and converting it back to an integer, adding it to the total sum.

Algorithm

  • Initialize a variable totalSum to 0.
  • Loop through each num in the nums array.
  • For each num, find its encrypted value:
    • Convert num to its string representation, s.
    • Find the largest digit character, maxDigitChar, by iterating through s.
    • Get the length of the string, len.
    • Construct the encrypted number. A simple way is to build a new number by repeatedly multiplying by 10 and adding the integer value of maxDigitChar.
  • Add the encrypted value to totalSum.
  • After the loop, return totalSum.

Walkthrough

The core idea is to process each number individually, find its encrypted form, and add it to a running sum. The encryption process is simplified by converting the number to a string, which allows for easy iteration over its digits.

The algorithm is as follows:

  1. Initialize a variable totalSum to 0.
  2. Iterate through each number num in the input array nums.
  3. For each num, we find its encrypted value using a helper function, encrypt(num).
  4. The encrypt(num) function works as follows:
    • Convert the integer num to its string representation, s.
    • Find the largest digit in s. This can be done by iterating through the characters of the string and keeping track of the maximum character seen so far.
    • The encrypted number will have the same number of digits as the original number, but all digits will be the largest digit. We can construct this number by starting with 0 and in a loop, multiplying by 10 and adding the max digit for each digit in the original number.
  5. Add the returned encrypted value to totalSum.
  6. After iterating through all numbers, totalSum will hold the final result.

Here is a Java implementation of this approach:

class Solution {    public long sumOfEncryptedInt(int[] nums) {        long totalSum = 0;        for (int num : nums) {            totalSum += encrypt(num);        }        return totalSum;    }     private int encrypt(int x) {        String s = Integer.toString(x);        char maxDigitChar = '0';        for (char c : s.toCharArray()) {            if (c > maxDigitChar) {                maxDigitChar = c;            }        }         int encryptedNum = 0;        int maxDigit = maxDigitChar - '0';        for (int i = 0; i < s.length(); i++) {            encryptedNum = encryptedNum * 10 + maxDigit;        }        return encryptedNum;    }}

Complexity

Time

O(N * D), where N is the number of elements in `nums` and D is the maximum number of digits in an element. For each number, we convert it to a string (O(D)), iterate through its digits (O(D)), and build the new number (O(D)).

Space

O(D), where D is the maximum number of digits in an element. This is for storing the string representation of the number. Since D is small and bounded by the constraints (max 4 for nums[i] <= 1000), this is effectively O(1) constant space.

Trade-offs

Pros

  • Simple to understand and implement.

  • The logic directly follows the problem description, making it very intuitive.

Cons

  • Involves type conversions (integer to string and back), which can be less efficient than pure arithmetic operations due to object creation and memory allocation overhead.

  • May be slightly slower in practice for very large inputs, although for the given constraints the difference is negligible.

Solutions

class Solution {public  int sumOfEncryptedInt(int[] nums) {    int ans = 0;    for (int x : nums) {      ans += encrypt(x);    }    return ans;  }private  int encrypt(int x) {    int mx = 0, p = 0;    for (; x > 0; x /= 10) {      mx = Math.max(mx, x % 10);      p = p * 10 + 1;    }    return mx * p;  }}

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 →

Next problem