[Golang] Power digit sum - Problem 16 - Project Euler
Problem: [1]
215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?
Solution:
We use large number addition [2] and the following formula:
2n = 2n − 1 + 2n − 1
The result is:
21000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
sum of digits = 1366
package main
import (
"fmt"
)
const MaxDigits = 350
const BASE = 10
func MakePositiveInt(s string) (n [MaxDigits]int) {
// make n zero
for i := 0; i < MaxDigits; i++ {
n[i] = 0
}
for index, digit := range s {
i := len(s) - index - 1
switch digit {
case '0':
n[i] = 0
case '1':
n[i] = 1
case '2':
n[i] = 2
case '3':
n[i] = 3
case '4':
n[i] = 4
case '5':
n[i] = 5
case '6':
n[i] = 6
case '7':
n[i] = 7
case '8':
n[i] = 8
case '9':
n[i] = 9
default:
panic("invalid digit in number string")
}
}
return
}
func AddPositiveInt(a, b [MaxDigits]int) (c [MaxDigits]int) {
var carry, sum = 0, 0
// make c zero
for i := 0; i < MaxDigits; i++ {
c[i] = 0
}
for i := 0; i < MaxDigits; i++ {
sum = a[i] + b[i] + carry
if sum >= BASE {
carry = 1
sum -= BASE
} else {
carry = 0
}
c[i] = sum
}
if carry != 0 {
panic("overflow in addition")
}
return
}
func PrintPositiveInt(a [MaxDigits]int) {
isLeadingZero := true
for i := MaxDigits - 1; i >= 0; i-- {
if isLeadingZero && a[i] == 0 {
continue
} else {
isLeadingZero = false
fmt.Print(a[i])
}
}
fmt.Println("\n")
}
func main() {
result := MakePositiveInt("2")
for i := 1; i < 1000; i++ {
result = AddPositiveInt(result, result)
}
PrintPositiveInt(result)
sum := 0
for i := 0; i < MaxDigits; i++ {
sum += result[i]
}
fmt.Println(sum)
}
Tested on: Go Playground
References:
[1] | Power digit sum - Problem 16 - Project Euler |
[2] | [Golang] Large Positive Integer Addition |