Instantly share code, notes, and snippets.

# ChristianSiegert/challenge-2012-06-15-a.go Created Jun 16, 2012

What would you like to do?
Solutions written in Go for challenge 2012-06-15 on ProgrammingPraxis.com
 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 }
 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 }
 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 }
Owner

### ChristianSiegert commented Jun 16, 2012

 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.