Skip to content

Instantly share code, notes, and snippets.

@ChristianSiegert
Created June 16, 2012 16:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ChristianSiegert/2941907 to your computer and use it in GitHub Desktop.
Save ChristianSiegert/2941907 to your computer and use it in GitHub Desktop.
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
}
@ChristianSiegert
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment