Problem #1

Problem link
Solution:

package main

func main() {
    i, sum := 0, 0
    for i < 1000 {
        if i%3 == 0 || i%5 == 0 {
            sum += i
        }
        i++
    }
    println(sum)
}

Result: 233168
Time: 0m0.003s

Problem #2

Problem link
Solution:

package main

func main() {
    a, b, sum := 1, 2, 0
    for b < 4000000 {
        if b%2 == 0 {
            sum += b
        }
        a, b = b, a+b
    }
    println(sum)
}

Result: 4613732
Time: 0m0.003s

Problem #3

Problem link
Solution:

package main

func main() {
    target := int64(600851475143)
    arr := make([]bool, 10000)
    prime := 3
    var k int
    for {
        for k = 2 * prime; k < len(arr); k += prime {
            arr[k] = true
        }
        for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
        }
        if k < len(arr) {
            prime = k
            if target%int64(k) == 0 {
                target = target / int64(k)
                if target == 1 {
                    println(k)
                    return
                }
            }
        } else {
            break
            //prevent infinite loop in case the answer
            //is not less than 10000
        }
    }
}

Result: 6857
Time: 0m0.003s

Problem #4

Problem link
Solution:

package main

import (
    "strconv"
)

func isPalindrome(input string) bool {
    for i := 0; i < len(input)/2; i++ {
        if input[i] != input[len(input)-1-i] {
            return false
        }
    }
    return true
}

func main() {
    max, mul := 0, 0
    for i := 100; i < 1000; i++ {
        for j := i; j < 1000; j++ {
            mul = i * j
            if isPalindrome(strconv.Itoa(mul)) && mul > max {
                max = mul
            }
        }
    }
    println(max)
}

Result: 906609
Time: 0m0.304s

Problem #5

Problem link
Solution:

package main

func main() {
    primes := []int{2, 3, 5, 7, 11, 13, 17, 19}
    result := 1
    var divisor int
    for i := range primes {
        divisor = primes[i]
        for divisor <= 20 {
            divisor *= primes[i]
        }
        divisor /= primes[i]
        result *= divisor
    }
    println(result)
}

Result: 232792560
Time: 0m0.003s

Problem #6

Problem link
Solution:

package main

func main() {
    result := ((100*101)/2)*((100*101)/2) - ((100 * 101 * 201) / 6)
    println(result)
}

Result: 25164150
Time: 0m0.003s

Problem #7

Problem link
Solution:

package main

func main() {
    arr := make([]bool, 105000)
    arr[0], arr[1] = true, true
    count, prime := 2, 3
    var k int
    for {
        for k = 2 * prime; k < len(arr); k += prime {
            arr[k] = true
        }
        for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
        }
        if k < len(arr) {
            prime = k
            count++
            if count == 10001 {
                println(prime)
                break
            }
        } else {
            break
        }
    }
}

After learning that the result is 104743, size of the boolean array is dropped down to 105000

Result: 104743
Time: 0m0.006s

Problem #8

Problem link
Solution:

package main

import "strconv"

func main() {
    number := "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
    largestPro := 0
    for i := 0; i < len(number)-5; i++ {
        localPro := 1
        for j := i; j < i+5; j++ {
            num, _ := strconv.Atoi(string(number[j]))
            localPro *= num
        }
        if localPro > largestPro {
            largestPro = localPro
        }
    }
    println(largestPro)
}

Result: 40824
Time: 0m0.008s

Problem #9

Problem link
Solution:

package main

import "math"

func isSquare(num int) (bool, int) {
    sqrt := int(math.Sqrt(float64(num)))
    if sqrt*sqrt == num {
        return true, sqrt
    }
    return false, -1
}

func main() {
loop:
    for a := 1; a < 500; a++ {
        for b := a; b < 500; b++ {
            result, c := isSquare(a*a + b*b)
            if result && a+b+c == 1000 {
                println(a * b * c)
                break loop
            }
        }
    }
}

Result: 31875000
Time: 0m0.016s

Problem #10

Problem link
Solution:

package main

func main() {
    arr := make([]bool, 2000000)
    arr[0], arr[1] = true, true
    sum, prime := int64(5), 3
    var k int
    for {
        for k = 2 * prime; k < len(arr); k += prime {
            arr[k] = true
        }
        for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
        }
        if k < len(arr) {
            prime = k
            sum += int64(k)
        } else {
            break
        }
    }
    println(sum)
}

Result: 142913828922
Time: 0m0.055s

Problem #11

Problem link
Solution:

package main

import (
    "strconv"
    "io/ioutil"
    "strings"
)

func main() {
    fileBuf, err := ioutil.ReadFile("011_input.txt")
    if err != nil {
        panic(err.String())
    }
    fileStr := string(fileBuf)
    lines := strings.Split(fileStr, "\n", 20)
    arr := make([][]uint, 20)
    var strArr []string
    for i := range lines {
        arr[i] = make([]uint, 20)
        strArr = strings.Split(lines[i], " ", 20)
        for j := range arr[i] {
            intvalue, _ := strconv.Atoi(strArr[j])
            arr[i][j] = uint(intvalue)
        }
    }
    max := uint(0)
    //left to right
    for i := range arr {
        for j := 0; j < 17; j++ {
            mul := arr[i][j] * arr[i][j+1] * arr[i][j+2] * arr[i][j+3]
            if mul > max {
                max = mul
            }
        }
    }
    //up to down
    for i := 0; i < 17; i++ {
        for j := range arr[i] {
            mul := arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j]
            if mul > max {
                max = mul
            }
        }
    }
    //first diagonal
    for i := 0; i < 17; i++ {
        for j := 0; j < 17; j++ {
            mul := arr[i][j] * arr[i+1][j+1] * arr[i+2][j+2] * arr[i+3][j+3]
            if mul > max {
                max = mul
            }
        }
    }
    //second diagonal
    for i := 3; i < 20; i++ {
        for j := 0; j < 17; j++ {
            mul := arr[i][j] * arr[i-1][j+1] * arr[i-2][j+2] * arr[i-3][j+3]
            if mul > max {
                max = mul
            }
        }
    }
    println(max)
}

Input file is renamed as 011_input.txt.

Result: 70600674
Time: 0m0.005s

Problem #12

Problem link
Solution:

package main

import (
    "math"
)

func main() {
    divisors := 1
    triangleN := uint64(1)
    for i := 2; divisors < 500; i++ {
        triangleN += uint64(i)
        divisors = noOfDivisors(triangleN)
    }
    println(triangleN)
}

func noOfDivisors(number uint64) int {
    counter := 0
    limit := uint64(math.Sqrt(float64(number)))
    for i := 1; uint64(i) <= limit; i++ {
        if number%uint64(i) == 0 {
            counter += 2
        }
    }
    return counter
}

Result: 76576500
Time: 0m1.010s

Problem #13

Problem link
Solution:

package main

import (
    "io/ioutil"
    "strconv"
    "strings"
)

func main() {
    fileBuf, err := ioutil.ReadFile("013_input.txt")
    if err != nil {
        panic(err.String())
    }
    fileStr := string(fileBuf)
    lines := strings.Split(fileStr, "\n", 100)
    result := ""
    carryout, digit := 0, 0
    for i := 49; i >= 0; i-- {
        sum := carryout
        for j := range lines {
            num, _ := strconv.Atoi(string(lines[j][i]))
            sum += num
        }
        digit = sum % 10
        carryout = sum / 10
        result = strconv.Itoa(digit) + result
    }
    result = strconv.Itoa(carryout) + result
    println(result[0:10])
}

Result: 5537376230
Time: 0m0.010s

Problem #14

Problem link
Solution:

package main

func main() {
    //allocate 4 MB of space at once
    arr := make([]int, 1000000)
    max, maxLoc, notFound, cur, steps := 0, 0, true, uint64(0), 0
    for i := 1; i < 1000000; i++ {
        notFound = true
        cur = uint64(i)
        steps = 0
        for notFound {
            if cur == 1 {
                notFound = false
                arr[i] = steps
                if steps > max {
                    max = steps
                    maxLoc = i
                }
            } else if cur < uint64(i) {
                notFound = false
                steps = steps + arr[cur]
                arr[i] = steps
                if steps > max {
                    max = steps
                    maxLoc = i
                }
            } else {
                if cur%2 == 0 {
                    cur /= 2
                } else {
                    cur = 3*cur + 1
                }
            }
            steps++
        }
    }
    println(max, maxLoc)
}

Result: 837799
Time: 0m0.271s

Problem #15

Problem link
Solution:

package main

var arr [][]uint64

func main() {
    arr = make([][]uint64, 21)
    for i := range arr {
        arr[i] = make([]uint64, 21)
        for j := range arr[i] {
            arr[i][j] = uint64(0)
        }
    }
    arr[20][20] = uint64(1)
    println(noOfRoutes(0, 0))
}

func noOfRoutes(i, j int) uint64 {
    if arr[i][j] != uint64(0) {
        return arr[i][j]
    }
    var result uint64
    if i < 20 && j < 20 {
        result = noOfRoutes(i+1, j) + noOfRoutes(i, j+1)
    } else if i < 20 && j == 20 {
        result = noOfRoutes(i+1, j)
    } else {
        result = noOfRoutes(i, j+1)
    }
    arr[i][j] = result
    return result
}

Result: 137846528820
Time: 0m0.003s

Problem #16

Problem link
Solution:

package main

import (
    "strconv"
)

func main() {
    input := "2"
    for i := 0; i < 999; i++ {
        input = multipyByTwo(input)
    }
    println(sumUpDigits(input))
}

func sumUpDigits(input string) int {
    result, digit := 0, 0
    for i := range input {
        digit, _ = strconv.Atoi(string(input[i]))
        result += digit
    }
    return result
}

func multipyByTwo(input string) string {
    result, carryout, digit := "", 0, 0
    for i := len(input) - 1; i >= 0; i-- {
        digit, _ = strconv.Atoi(string(input[i]))
        digit = digit*2 + carryout
        carryout = digit / 10
        digit = digit % 10
        result = strconv.Itoa(digit) + result
    }
    if carryout > 0 {
        result = strconv.Itoa(carryout) + result
    }
    return result
}

Result: 1366
Time: 0m0.228s

Problem #17

Problem link
Solution:

package main

func main() {
    sum := 0
    for i := 0; i < 1000; i++ {
        sum += lengthNumber(i)
    }
    println(sum + len("onethousand"))
}

func lengthNumber(number int) int {
    switch number {
    case 0:
        return 0
    case 1:
        return 3 //one
    case 2:
        return 3 //two
    case 3:
        return 5 //three
    case 4:
        return 4 //four
    case 5:
        return 4 //five
    case 6:
        return 3 //six
    case 7:
        return 5 //seven
    case 8:
        return 5 //eight
    case 9:
        return 4 //nine
    case 10:
        return 3 //ten
    case 11:
        return 6 //eleven
    case 12:
        return 6 //twelve
    case 13:
        return 8 //thirteen
    case 14:
        return 8 //fourteen
    case 15:
        return 7 //fifteen
    case 16:
        return 7 //sixteen
    case 17:
        return 9 //seventeen
    case 18:
        return 8 //eighteen
    case 19:
        return 8 //nineteen
    case 20:
        return 6 //twenty
    case 30:
        return 6 //thirty
    case 40:
        return 5 //forty
    case 50:
        return 5 //fifty
    case 60:
        return 5 //sixty
    case 70:
        return 7 //seventy
    case 80:
        return 6 //eighty
    case 90:
        return 6 //ninety
    }
    if number < 100 {
        return lengthNumber(number-(number%10)) + lengthNumber(number%10)
    }
    if number%100 == 0 {
        return lengthNumber(number/100) + 7
    }
    return lengthNumber(number/100) + 10 + lengthNumber(number%100)
}

Result: 21124
Time: 0m0.003s

Problem #18

Problem link
Solution:

package main

import (
    "io/ioutil"
    "strconv"
    "strings"
)

var arr [][]int
var bests [][]int

func main() {
    fileBuf, err := ioutil.ReadFile("018_input.txt")
    if err != nil {
        panic(err.String())
    }
    fileStr := strings.Trim(string(fileBuf), "")
    oneDArrStr := strings.Split(fileStr, "\n", -1)
    var line []string
    arr = make([][]int, 15)
    bests = make([][]int, len(arr))
    for i := range arr {
        line = strings.Split(oneDArrStr[i], " ", -1)
        arr[i] = make([]int, len(line))
        bests[i] = make([]int, len(arr[i]))
        for j := range line {
            arr[i][j], _ = strconv.Atoi(line[j])
            bests[i][j] = -1
        }
    }
    println(bestSum(0, 0))
}

func bestSum(i, j int) int {
    var result int
    if bests[i][j] != -1 {
        result = bests[i][j]
    } else if i == len(arr)-1 {
        result = arr[i][j]
        return arr[i][j]
    } else {
        sumLeft, sumRight := bestSum(i+1, j), bestSum(i+1, j+1)
        if sumLeft > sumRight {
            result = arr[i][j] + sumLeft
        } else {
            result = arr[i][j] + sumRight
        }
    }
    bests[i][j] = result
    return result
}

Tree is read from a file named as 018_input.txt and also memoization is used for this problem.

Result: 1074
Time: 0m0.005s

Problem #19

Problem link
Solution:

package main

var months []int
var count int

func main() {
    months = make([]int, 12)

    //calculate first days of the months in 1900
    daysInMonths := []int{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30}
    months[0] = 0
    for i := range daysInMonths {
        months[i+1] = (months[i] + daysInMonths[i]) % 7
    }

    count = 0
    for year := 1900; year < 2000; year++ {
        for i := range months {
            if (year%4 == 0 && i <= 1) || ((year+1)%4 == 0 && i > 1) {
                months[i] = (months[i] + 366) % 7
            } else {
                months[i] = (months[i] + 365) % 7
            }
            if months[i] == 6 {
                count++
            }
        }
    }
    println(count)
}

Result: 171
Time: 0m0.003s

Problem #20

Problem link
Solution:

package main

import (
    "big"
    "strconv"
)

func main() {
    mul := big.NewInt(1)
    for i := 2; i <= 100; i++ {
        mul.Mul(mul, big.NewInt(int64(i)))
    }
    result, digit := 0, 0
    for i := range mul.String() {
        digit, _ = strconv.Atoi(string(mul.String()[i]))
        result += digit
    }
    println(result)
}

Result: 648
Time: 0m0.023s