Solutions written in Go for challenge 2012-06-15 on ProgrammingPraxis.com

challenge-2012-06-15-a.go

package main

import (
	"fmt"
	"strconv"
)

func main() {
	fmt.Println("Question from: http://programmingpraxis.com/2012/06/15/counting-ones/")
	fmt.Println("Question: Consider a function f that takes a positive integer n and returns the number of 1s in the decimal representation of all the integers from 0 to n, inclusive. For example, f(13) = 6, for the numbers 1, 10, 11 (twice, for two 1s), 12 and 13. Notice that f(1) = 1. After 1, what is the next largest n for which f(n) = n?")

	for n := 2; n <= 200000; n++ {
		if n%10000 == 0 {
			fmt.Println("Checking n =", n)
		}

		if numberOfOnesInNumbersFromZeroTo(n) == n {
			fmt.Println("Answer:", n)
			return
		}
	}

	fmt.Println("Couldn't find answer.")
}

func numberOfOnesInNumbersFromZeroTo(n int) int {
	count := 0

	for i := 0; i <= n; i++ {
		iAsString := strconv.Itoa(i)

		for _, value := range iAsString {
			if value == 49 {
				count++
			}
		}
	}

	return count
}

challenge-2012-06-15-b.go

package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main() {
	fmt.Println("Question from: http://programmingpraxis.com/2012/06/15/counting-ones/")
	fmt.Println("Question: Consider a function f that takes a positive integer n and returns the number of 1s in the decimal representation of all the integers from 0 to n, inclusive. For example, f(13) = 6, for the numbers 1, 10, 11 (twice, for two 1s), 12 and 13. Notice that f(1) = 1. After 1, what is the next largest n for which f(n) = n?")

	for n := 2; n <= 200000; n++ {
		if n%10000 == 0 {
			fmt.Println("Checking n =", n)
		}

		if numberOfOnesInNumbersFromZeroTo(n) == n {
			fmt.Println("Answer:", n)
			return
		}
	}

	fmt.Println("Couldn't find answer.")
}

func numberOfOnesInNumbersFromZeroTo(n int) int {
	count := 0

	for i := 0; i <= n; i++ {
		iAsString := strconv.Itoa(i)
		count += strings.Count(iAsString, "1")
	}

	return count
}

challenge-2012-06-15-c.go

package main

import (
	"fmt"
	"strconv"
	"strings"
)

type Counter struct {
	lastN        int
	numberOfOnes int
}

var counter = &Counter{}

func main() {
	fmt.Println("Question from: http://programmingpraxis.com/2012/06/15/counting-ones/")
	fmt.Println("Question: Consider a function f that takes a positive integer n and returns the number of 1s in the decimal representation of all the integers from 0 to n, inclusive. For example, f(13) = 6, for the numbers 1, 10, 11 (twice, for two 1s), 12 and 13. Notice that f(1) = 1. After 1, what is the next largest n for which f(n) = n?")

	for n := 2; n <= 200000; n++ {
		if n%10000 == 0 {
			fmt.Println("Checking n =", n)
		}

		if numberOfOnesInNumbersFromZeroTo(n) == n {
			fmt.Println("Answer:", n)
			return
		}
	}

	fmt.Println("Couldn't find answer.")
}

func numberOfOnesInNumbersFromZeroTo(n int) int {
	// If we calculated numberOfOnes for n-1, simply count ones in n and add
	// result to numberOfOnes.
	if n-1 == counter.lastN {
		nAsString := strconv.Itoa(n)
		counter.numberOfOnes += strings.Count(nAsString, "1")
		counter.lastN = n
		return counter.numberOfOnes
	}

	numberOfOnes := 0

	// Else, calculate numberOfOnes by counting ones in all numbers from 0 to n.
	for i := 0; i <= n; i++ {
		iAsString := strconv.Itoa(i)
		numberOfOnes += strings.Count(iAsString, "1")
	}

	counter.numberOfOnes = numberOfOnes
	counter.lastN = n
	return counter.numberOfOnes
}

Console output from all programs:

$ go run challenge-2012-06-15-x.go 
Question from: http://programmingpraxis.com/2012/06/15/counting-ones/
Question: Consider a function f that takes a positive integer n and returns the number of 1s in the decimal representation of all the integers from 0 to n, inclusive. For example, f(13) = 6, for the numbers 1, 10, 11 (twice, for two 1s), 12 and 13. Notice that f(1) = 1. After 1, what is the next largest n for which f(n) = n?
Checking n = 10000
Checking n = 20000
Checking n = 30000
Checking n = 40000
Checking n = 50000
Checking n = 60000
Checking n = 70000
Checking n = 80000
Checking n = 90000
Checking n = 100000
Checking n = 110000
Checking n = 120000
Checking n = 130000
Checking n = 140000
Checking n = 150000
Checking n = 160000
Checking n = 170000
Checking n = 180000
Checking n = 190000
Answer: 199981

Program challenge-2012-06-15-c.go is by far the fastest one of these three.