[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

Run Code on Go Playground

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