Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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

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
Something went wrong with that request. Please try again.