# Find the Sum of Encrypted Integers
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-sum-of-encrypted-integers)
Canonical: https://scaleengineer.com/dsa/problems/find-the-sum-of-encrypted-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Larsen  Toubro](https://scaleengineer.com/companies/larsen-toubro)
---
## Problem
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
## Brute Force using String Conversion
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.
**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.
**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.
### Explanation
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:
```java
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;
    }
}
```
### 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`.

## Optimized Arithmetic Approach
This approach avoids string conversions entirely and relies on mathematical operations to achieve the same result. For each number, it iteratively extracts digits using the modulo and division operators to find the largest digit and count the number of digits. Then, it mathematically constructs the encrypted number and adds it to the total sum.
**Time:** O(N * D), where N is the number of elements in `nums` and D is the maximum number of digits in an element (D is proportional to log10 of the number). This is asymptotically the same as the string approach, but with a lower constant factor, making it faster in practice. · **Space:** O(1). This approach uses only a few variables for calculations, requiring constant extra space regardless of the input size.
**Pros:** More efficient as it avoids the overhead of string creation and manipulation.; Relies solely on fast, primitive arithmetic operations.; Uses constant extra space.
**Cons:** The logic can be slightly more complex to reason about compared to the direct string manipulation approach.
### Explanation
This approach improves upon the first by avoiding the overhead of string conversions. It uses pure arithmetic operations (modulo and division) to inspect the digits of each number, which is generally more performant.

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:
    *   Make a copy of the number, say `temp = num`.
    *   Initialize `maxDigit = 0` and `numDigits = 0`.
    *   Use a `while` loop on `temp` until it becomes 0. In each step:
        *   Extract the last digit using the modulo operator: `digit = temp % 10`.
        *   Update `maxDigit = Math.max(maxDigit, digit)`.
        *   Increment `numDigits`.
        *   Update `temp` by integer division: `temp /= 10`.
    *   After the loop, we have the largest digit (`maxDigit`) and the total number of digits (`numDigits`).
    *   Construct the encrypted number. For example, if `maxDigit` is 5 and `numDigits` is 3, the result is 555. This can be built in a loop: `result = 0; for i=0 to numDigits-1: result = result * 10 + maxDigit`.
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:
```java
class Solution {
    public long sumOfEncryptedInt(int[] nums) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += encrypt(num);
        }
        return totalSum;
    }

    private int encrypt(int x) {
        if (x < 10) { // Optimization for single-digit numbers
            return x;
        }
        
        int maxDigit = 0;
        int numDigits = 0;
        int temp = x;
        
        while (temp > 0) {
            int digit = temp % 10;
            if (digit > maxDigit) {
                maxDigit = digit;
            }
            numDigits++;
            temp /= 10;
        }
        
        int encryptedNum = 0;
        for (int i = 0; i < numDigits; i++) {
            encryptedNum = encryptedNum * 10 + maxDigit;
        }
        return encryptedNum;
    }
}
```
### Algorithm
- Initialize `totalSum = 0`.
- For each `num` in `nums`:
  - Initialize `maxDigit = 0`, `numDigits = 0`, and a copy `temp = num`.
  - While `temp > 0`:
    - Extract the last digit: `digit = temp % 10`.
    - Update the max digit: `maxDigit = max(maxDigit, digit)`.
    - Increment the digit count: `numDigits++`.
    - Remove the last digit: `temp /= 10`.
  - Initialize `encryptedNum = 0`.
  - Loop `numDigits` times: `encryptedNum = encryptedNum * 10 + maxDigit`.
  - Add `encryptedNum` to `totalSum`.
- Return `totalSum`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int sumOfEncryptedInt(vector<int> &nums) {
    auto encrypt = [&](int x) {
      int mx = 0, p = 0;
      for (; x; x /= 10) {
        mx = max(mx, x % 10);
        p = p * 10 + 1;
      }
      return mx * p;
    };
    int ans = 0;
    for (int x : nums) {
      ans += encrypt(x);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def sumOfEncryptedInt(self, nums: List[int]) -> int: def encrypt(x: int) -> int: mx = p = 0 while x: x, v = divmod(x, 10) mx = max(mx, v) p = p * 10 + 1 return mx * p return sum(encrypt(x) for x in nums)

```