public
Last active

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

  • Download Gist
challenge-2012-06-15-a.go
Go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
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
Go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
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
Go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
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.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.