Mai Amin Mai Amin - 2 months ago 5
C# Question

How can you count the occurrence of 1 from 1 to 99,999,999 (1 short of 100 million) and total up how many 1s were there

i started learn c# and in such task. i have already do it this is the code:

string y = "";
int count = 0;
string x = "";
string[] arr = new string[100000000];

for (int i = 0; i < 100000000; i++)
{
x = i.ToString() + x;
}

Console.WriteLine(x);

for (int j = 0; j < x.Length; j++)
{
y = x.Substring(j, 1);

switch (y)
{
case "1":
count ++;
break;

default:
break;
}
}

Console.WriteLine(count);


The code worked correctly in case of small range (0 to 1000) but when running it for a range of 100 million it does not produce any result (i waited for while but no output)plus it looks like my code is not efficient way. my question now is what is the problem in this code and if there was a better solution for this task.

Answer

I think your biggest problem is string concatenation. A big mistake C# newbies make is thinking that strings are mutable, because they behave that way to an external observer. In fact, they are treated as immutable in memory; every time x = i.ToString() + x executes in your loop, two new strings are created, one of them replacing the previous reference kept by X. i.ToString() and the old x value leave scope, but aren't removed from memory until the GC can get to them. So, this algorithm is making the memory-management layer of the runtime work uncommonly hard.

In addition, you have a 100-million-element array, arr, taking up space in the sandbox. This probably isn't really slowing you down, but it's certainly wasting memory given it's not used.

The "switch" statement is too much for what you want to do. The exact same operation can be specified more simply (and with fewer underlying operations) thusly: if(y=="1") count++;.

Lastly, if you want a single character from a string in most C-style languages, you can simply treat the string as an array of characters (which it is): y = x[j]; will give you the same result as y=x.Substring(j,1), it will just be a character variable instead of a one-character string, and it should be much faster because you're not spinning through the logic in the String.Substring() method.


Instead, you get the same result by just taking each string in order and counting the 1s in it, and adding that to a grand total. Your existing implementation will work if tweaked that way, but a little Linq will make the code cleaner (though not necessarily faster):

for(var i=1; i < 100000000; i++)
    count += i.ToString().Count(c=>c=='1');

You could even one-line it with a pure Linq solution:

var count = Enumerable.Range(1,99999999).Aggregate(0, (s, i) => s + i.ToString().Count(c=>c == '1'));

Breaking this down:

  • Enumerable.Range produces an "enumerable" (one-way iterable series) of incrementing integers starting with the first parameter and continuing until the second parameter's number of numbers have been produced.
  • Aggregate basically wraps a compounding loop; it takes a "seed" value (0), passes that in as the first parameter of the anonymous method along with the first element of the source collection, then takes the result of that method and feeds it back into the lambda statement along with the next element, and so on until it's done this for every element.
  • The lambda statement (s, i) => s + i.ToString().Count(c=>c == '1') takes two integers ("seed" and "integer"), turns the integer into a string, counts the number of '1' characters in that string, and adds that total to s. The returned value of the lambda is that sum.

Other things to think about:

  • In the general case this may not work, but you know that no number greater than 99,999,991 in your series will have any '1' digits, so by continuing beyond that number you're just wasting time (not much in this case, but still).
  • String parsing isn't bad, but integer math is typically much faster. For each number, try dividing by 10, then modulo'ing by 10. This will produce each digit of the number, that you can compare with 1 and increment "count" if true. It will take more lines of code, but it will likely still work out faster than ToString()ing each number, as that requires more computational steps to determine the character value for each digit and put them together (and less memory, as integer values can be operated on more or less in place, so instead of needing a string for every number, you need three integer variables for the whole loop):

    var count = 0;
    for(var i=1; i<100000000; i++)
    { 
        var j = i;
        while(j > 0)
        {
            if(j % 10) == 1) 
                count++;
            j /= 10;
        }
    }