Question

3079. Find the Sum of Encrypted Integers

中文文档

Description

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

Solutions

Solution 1: 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)$.

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)

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

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

func sumOfEncryptedInt(nums []int) (ans int) {
  encrypt := func(x int) int {
    mx, p := 0, 0
    for ; x > 0; x /= 10 {
      mx = max(mx, x%10)
      p = p*10 + 1
    }
    return mx * p
  }
  for _, x := range nums {
    ans += encrypt(x)
  }
  return
}

function sumOfEncryptedInt(nums: number[]): number {
  const encrypt = (x: number): number => {
    let [mx, p] = [0, 0];
    for (; x > 0; x = Math.floor(x / 10)) {
      mx = Math.max(mx, x % 10);
      p = p * 10 + 1;
    }
    return mx * p;
  };
  return nums.reduce((acc, x) => acc + encrypt(x), 0);
}