英文:
Calculating the Time and Space Complexity of Maximum sum of two elements whose digit sum is equal
问题
fun maxSumDigits(arr: IntArray): Int {
val hashMap: MutableMap<Int, Int> = mutableMapOf()
var result = -1
for (element in arr) {
val sumDigit = digitsSum(element)
if (hashMap.containsKey(sumDigit)) {
result = max(result, hashMap[sumDigit]?.plus(element) ?: 0)
}
hashMap[sumDigit] = max(element, hashMap[sumDigit] ?: 0)
}
System.out.println(result)
return result
}
private fun digitsSum(num: Int): Int {
var n = num
var result = 0
while (n > 0) {
result += n % 10
n /= 10
}
return result
}
(Note: This is the code section you provided, translated and formatted for readability.)
英文:
I have an interview and i really want to know the space and the time complexity of this problem
I believe that the time complexity of this problem is an O(nlog(n)) but i'm not sure and the space complexity is really hard for me to figure out because it may depend on the input. is this right ?
fun maxSumDigits(arr : IntArray) : Int{
val hashMap : MutableMap<Int,Int> = mutableMapOf()
var result = -1
for (element in arr){
val sumDigit = digitsSum(element)
if (hashMap.containsKey(sumDigit)){
result = max(result, hashMap[sumDigit]?.plus(element) ?: 0)
}
hashMap[sumDigit] = max(element, hashMap[sumDigit] ?: 0)
}
System.out.println(result)
return result
}
private fun digitsSum(num: Int): Int {
var n = num
var result = 0
while (n > 0){
result += n % 10
n /= 10
}
return result
}
答案1
得分: 2
时间复杂度预期为O(n)，这有点奇怪。通常认为机器字（machine word）的大小是恒定的，而digitSum所花费的时间与此成比例 - O(1)。您将其重复进行n次，因此所有求和的时间复杂度为O(n)。哈希映射操作需要O(n)的预期时间。
奇怪的是，如果有一个规则，使得数组元素都介于0和n之间，那么任何n的最坏情况所需的时间会更少，但我们会说复杂度是O(n log n)，因为digitSum的复杂度会从O(1)变为O(log n)。限制输入会使求和时间以对数方式依赖于n。
空间复杂度仅为O(n)，用于在哈希映射中存储n个最大值。
英文:
The time complexity is expected O(n), which is a little odd. The size of a machine word is usually considered constant, and digitSum takes time proportional to that - O(1). You do it n times, so it's O(n) for all the sums. The hashmap operations takes O(n) expected time.
The strange thing is that if there was a rule that all of the array elements were between 0 and n, then the worst case for any n would take less time, but we would say that the complexity is O(n log n), because digitSum would be O(log n) instead of O(1). Restricting the input makes the summation time depend on n in a logarithmic way.
The space complexity is just O(n) to store the n maximums in the hashmap.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论