[Golang] Power digit sum - Problem 16 - Project Euler
source link: http://siongui.github.io/2017/12/29/go-power-digit-sum-problem-16-project-euler/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Golang] Power digit sum - Problem 16 - Project Euler
December 29, 2017
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:
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK