Kotlin. Beats 100% (8 ms). IntArray to count sums.
CodeApproachNumbers from the Int range cannot exceed the value 9,999,999,999.The sum of 10 nines cannot be greater than 100, so we can freely use the IntArray a
![image.png](https://assets.leetcode.com/users/images/82c2ea12-2a55-407d-be28-75f55224d70b_1739373533.7690551.png)

# Code
```kotlin []
class Solution {
    fun maximumSum(nums: IntArray): Int {
        var max = -1
        val map = IntArray(82) { Int.MIN_VALUE }
        for (n in nums) {
            val sum = getSumOfDigits(n)
            if (map[sum] + n > max) max = map[sum] + n
            if (n > map[sum]) map[sum] = n
        }
        return max
    }

    private fun getSumOfDigits(n: Int): Int {
        var result = 0
        var n = n
        while (n > 0) {
            result += cached[n % 1000]
            n /= 1000
        }
        return result
    }

    companion object {
        val cached = IntArray(1000) {
            var result = 0
            var n = it
            while (n > 0) {
                result += n % 10
                n /= 10
            }
            result
        }
    }
}
```

# Approach

Numbers from the Int range cannot exceed the value 9,999,999,999.

The sum of 10 nines cannot be greater than 100, so we can freely use the IntArray array instead of the slower HashMap, which under the hood does a lot of extra work to find the bucket and allocate additional objects.

Just in case, let me remind you that the formula for calculating the bucket index in Java's HashMap is as follows:

```
val bucketIndex = (key.hashCode() xor key.hashCode() shr 16) and (buckets.size - 1)
```

While we don't need to calculate the required array index at all :)

The next step in optimization is calculating the sum of digits. There is a non-zero probability that when calculating the sum of digits, we will come across the same combinations of triplets of digits, for example:
7 543 and 9 543.

For such cases, we can create a static pre-computed cache in advance and take values ​​from there, sorting through the numbers not by individual digits, but by triplets of digits at once, which will be significantly faster.

The cache size of 1000 cells turned out to be optimal according to measurements - further increase in the cache size does not lead to a gain in speed (10000 for example), but slows down the time at the start for calculating the cache and worsens the algorithm performance.

# Alternative approaches

1. Solution option without caching

![image.png](https://assets.leetcode.com/users/images/701ad407-21ce-4404-aa83-f08ae7ad53ff_1739354207.2633035.png)

```
class Solution {
    fun maximumSum(nums: IntArray): Int {
        var max = -1
        val map = IntArray(82) { Int.MIN_VALUE }
        for (n in nums) {
            val sum = getSumOfDigits(n)
            max = Math.max(max, map[sum] + n)
            map[sum] = Math.max(map[sum], n)
        }
        return max
    }

    private fun getSumOfDigits(n: Int): Int {
        var result = 0
        var n = n
        while (n > 0) {
            result += n % 10
            n /= 10
        }
        return result
    }
}
```
['Kotlin']