Create a programs that counts the 0's in numbers from 0 to a billion [duplicate]

Question

This will be my very first post on stackexchange so bear with me.

Create a program that counts from 0 to 1,000,000,000. Now the trick is to not print all these characters but to only print how many zeroes are in that number. And keep track of the total amount of zeroes you've encountered. For example

10

Will output;

1
2

because 10 has 1 zero in it. The two represents how many 0's you've seen in total, in this case the only zero you have encountered previously is 0 itself so you've seen a total of 2 zeroes. The highest score will be given to the shortest code (no surprise here).

I hope that this is not too easy and that I've posted enough information, given the fact that I'm completely new here I'm not entirely sure about this.

Answer 1

Python (brute force, 80 chars)

def r(n):
    l=[str(i).count('0') for i in xrange(n+1)]
    return l[-1],sum(l)

Just to asure, i got the task right, it evaluates to:

r(10)
>>> (1, 2)
r(1000000000)
>>> (9, 788888899)

Answer 2

(Oracle) SQL, 146 144 chars / 122 chars

SELECT*FROM(SELECT l,SUM(REGEXP_COUNT(l,'0'))d FROM(SELECT LEVEL-1l FROM dual CONNECT BY LEVEL<=&a+1)GROUP BY ROLLUP(l))WHERE &a=l OR l IS NULL;

Expanded:

SELECT *
FROM (
   SELECT
      l,
      SUM(REGEXP_COUNT(l, '0')) d
   FROM (
      SELECT LEVEL - 1 l
      FROM dual
      CONNECT BY LEVEL <= &a + 1
   )
   GROUP BY ROLLUP(l)
)
WHERE &a = l
   OR l IS NULL;

Edit: no need to name the column, and * doesn't need spaces around it.

---

Okay, so we need it for all numbers from 0 to n. Let me put on my thinking cap... Try

SELECT c,SUM(c)OVER(ORDER BY l)FROM(SELECT l,REGEXP_COUNT(l,'0')c FROM(SELECT LEVEL-1l FROM dual CONNECT BY LEVEL<=&a+1));

Expanded:

SELECT
   c,
   SUM(c) OVER(ORDER BY l)
FROM (
   SELECT 
      l,
      REGEXP_COUNT(l, '0') c
   FROM (
      SELECT LEVEL - 1 l
      FROM dual
      CONNECT BY LEVEL <= &a + 1
   )
);

Answer 3

C, 90 bytes

r;i;j;main(t){for(;i<=10e8;j=++i){for(r=0;j;j/=10)j%10||r++;t+=r;}printf("%d\n%d\n",r,t);}

ungolfed:

r;i;j;main(t) {
    for (;i<=10e8;j=++i) {
        for (r=0;j;j/=10)
            j%10||r++;
        t+=r;
    }
    printf("%d\n%d\n",r,t);
}

Answer 4

GolfScript 34 32

0 10.(?,{`{48=},,}%{(.p@+.p\.}do

Explanation:

The initial 0 will be the counter for the number of 0s seen thus far. A billion is 10^9, and 10.(? generates a billion by taking 10, copying it, decrementing, and then exponentiating. The , then generates an array of all numbers for 0 to a billion - 1. If we need to include one billion, add a ) before the ,.

The next block takes a number, converts it to a string by doing ''+, then filtering down to the characters that equals '0' (ASCII value 48) by doing {48=}, and then counting the length of the array by doing ,. Map this block across all the numbers in our array with %.

The next block expects two elements on the stack: the total 0s seen, and then the array of 0-counts for each integer not yet printed. Each time the block is executed it pops the first element of the array with (, copies and then prints it with .p, moves the total counter to the front with @, adds the current number, and then rearranges the stack to be in the right order. The do will run this block until the array is empty.

Answer 5

APL (30)

Brute-forced. There is no lazy evaluation, so it generates the whole list from 0 to 1e9 at once. So you need at least a 7GB workspace, or it will just say WS FULL.

In case you don't have a huge server to use, the program can be proven to work by lowering 1e9 to a saner amount.

(⊃⌽Z),+/¯1↓Z←{'0'+.=⍕⍵}¨0,⍳1e9

Explanation:

• 0,⍳1e9: the list from 0 up to and including 1e9
• Z←{'0'+.=⍕⍵}¨: count the zeroes in each number, and store the list in Z.
• +/¯1↓Z: the sum of all but the last item in Z (the total amount of zeroes encountered)
• ⊃⌽Z: the last item in Z (the amount of zeroes in 1e9).

Answer 6

C# - 223 chars:

using System.Linq;class P{static void Main() { G(10); } static void G(int i){System.Console.Write("{0},{1}",i.ToString().Count(l => l == '0'),Enumerable.Range(0, i + 1).SelectMany(b => b.ToString()).Count(l => l == '0'));}}

Expanded:

using System.Linq;
class P
{
    static void Main() { G(10); } 
    static void G(int i)
    {
        System.Console.Write("{0},{1}", 
            i.ToString().Count(l => l == '0'), 
            Enumerable.Range(0, i + 1).SelectMany(b => b.ToString()).Count(l => l == '0'));
    }
}

Answer 7

Python 81 chars

def x(y):
    o=0
    for i in xrange(y+1):
        o+=`i`.count('0')
    print `y`.count('0'),o

Answer 8

J (33)

Warning: uses an ungodly amount of memory.

({:,+/@}:)(+/@('0'=":))"0 i.1e9+1

Explanation:

• i.1e9+1: generate a list of numbers from 0 up to and including 1e9.
• (+/@('0'=":))"0: for each number ("0), convert it to a string (#:), and see how many zeroes there are ('0'=).
• ({:,+/@}:): display the last item in the list ({:), followed by the sum of all but the last item in the list (+/@}:)