c help

[callumacrae]

So I suck at C and don't really understand it at all.

I'm trying to rewrite the following code into c:

<?php

for ($i = 1, $count = null; $i <= 500000000; $i++)
{
                $count .= substr_count($i, 1); 
}

echo $count;

So far I only have the following:

#include <stdio.h>

int main (int argc, const char * argv[])
{
	int i, num, count, total;
	
	total = 500000000;
	
	for (i = 1; i <= total; i++)
	{
		//generate num here
		count += num;
	}
	
	printf("The number 1 appears in %d a total %d times", total, count);
	return 0;
}

I have no idea how to cycle through a number and count how many times another number appears. Can anyone help me here please?

~Callum

[denzil]

ok I'll give it a shot. I don't do too much C programming besides on embedded systems (such as electronic devices) though.

I don't quite understand what you are asking. Please just clarify what you mean by cycle through a number. I'm actually thinking you mean count the number of single digit numbers making up a bigger number, so the number 1501, will contain two 1's, a 5 and a 0. Is this right?

I think the easiest method would perhaps be to use string handling -> convert it to a string and compare characters in the string. Give me some time, I'll post back soon. #added later: You could do it with string handling but I found the solution using modulus easier (see below).

Here is a java solution. It should be very similar to C. It works for my understanding of your problem. I'll try and code you a C version as well.

public class test{
  public static void main(String [] args)
  {
    int num = 33153;
        int printNum = num; //just a duplicate for printing
	 int myNumberToCount = 3;
	 int count = 0;
	 
	 while (num > 0)
	 {
	 	int a = num % 10;
	 	num /=10;
	 	if ( a == myNumberToCount)
		  count++;
	 }
	 System.out.printf("The number %d appears a total of %d in the number %d",myNumberToCount,count,printNum);
  }
}

what this does is take the modulus of the number by 10 to get the remainder. So if you had 101, it would take the remainder of it's division by 10, which is one (101/10 = 10 with a remainder of 1). If it equals the number you are looking for, increase the counter. Now divide the number by 10 so that next time we loop, it will be at the next digit.

To be honest, I don't even think your php can be correct. What you are currently doing is looping through 500000000 numbers (starting at one), and each time counts the number of 1's appearing a substring of that number, and concatenating (adding as a string) to your count variable.

Please just make sure of what you want, then state it clearly. If my above solution is correct just convert it to C and ask for help if you need any (the C solution will look very similar to the java one above).

[callumacrae]

Thats exactly what I wanted, thanks

I think the c would be almost exactly the same:

#include <stdio.h>

int main (int argc, const char * argv[])
{

	int num = 33153;
	int printNum = num;
	int myNumberToCount = 3;
	int count = 0;
	 
	while (num > 0)
	{
		int a = num % 10;
		num /=10;
		if ( a == myNumberToCount)
		{
			count++;
		}
	}
	printf("The number %d appears a total of %d in the number %d", myNumberToCount, count, printNum);
	return 0;
}

~Callum

[denzil]

Glad I could help let me know if there is anything else.

[callumacrae]

Final script...

#include <stdio.h>
#include <time.h>

int substr_count(int num, int search);

int main (int argc, const char * argv[])
{
	int search = 1;
	int total = 500000000;
	int count = 0;
	
	//take the time
	int start = time(NULL);
	
	printf("\nStarting now. Time at start: %d\n\n", start);
	
	for (int i = 1; i <= total; i++)
	{
		count += substr_count(i, search);
	}
	
	printf("The number %d appeared %d times\n", search, count);
	
	int end = time(NULL);
	printf("Completed, took %i seconds\n\n", end - start);
	
	return 0;
}

//yeeaah so im stealing the PHP name...
int substr_count(int num, int search)
{
	int count = 0;

	while (num > 0)
	{
		int a = num % 10;
		num /= 10;
		if (a == search)
		{
			count++;
		}
	}
	return count;
}

That took 34 seconds to run, while it took PHP about 5 minutes to do exactly the same thing :D

~Callum

[denzil]

Oh now I fully get what you wanted to do. What is the point of this if I may ask? :P

I expected php to be slower than C (I'm sure you have too), but damn, that's quite a lot faster. Did you run the php and C on the same machine?

It was an interesting challenge. Let me know if you have more.

*edit: Oh, of course. It's because substring count is string handling. It has to do character comparisons and things like that too (on top of the fact that Php will be slower - not saying php sucks though, I use it. Great for web design). I believe my code is more efficient :P

[callumacrae]

Run it, you'll see what the point is

~Callum

[denzil]

Oh cool. Interesting number I see. Thought it was just something random.

[misson]

If you care about the result more than the method, an equivalent function can be written that runs in the same time as a power function (possibly O(log(n))) rather than O(n*log(n)).

To start, we solve the related problem of counting all 1s in all numbers between 0 and 10^x, exclusive (where "^" means exponentiation). Let this number be dc(x) (think "digit count"). Thinking recursively, note dc(1)=1. Assume we can calculate dc(x-1). We can then calculate dc(x) by breaking up the 1s we need to count into leading digits and trailing digits. That is, count the leading 1s in numbers 10^(x-1) through 2*10^(x-1) - 1, inclusive (below, these numbers are written as the patterns "10*" and "19*"), and calculate the trailing 1s in all the numbers between 0 and 10^x, which can be done using dc(x-1). With double angle brackets indicating the sections of numbers to count, dc(x) can be calculated by counting «1»0* .. «1»9* and 0«0*» .. 9«9*». In the first case, there are 10^(x-1) numbers, hence 10^(x-1) leading ones. In the latter case, there are dc(x-1) trailing digits of interest for any given leading digit, and 10 leading digits, for a total of 10 * dc(x-1) digits of interest.

dc(1) = 1
        («1»0* .. «1»9*)     (0«0*» .. 9«9*»)
dc(x) =    10 ^ (x-1)    +     10 * dc(x-1)

We can do one better, writing dc as the explicit function "x * 10^(x-1)" rather than a recursive function. Note dc(1) = 1 = 1 * 10^0. Now assume dc(x-1) = (x-1) * 10^(x-2). Then

dc(x) = 10 ^ (x-1) + 10 * dc(x-1) 
      = 10 ^ (x-1) + 10 * ((x-1) * 10^(x-2)) 
      = (1 + x-1)  * 10 ^ (x-1)
      = x * 10^(x-1)                          QED

Note that though we set out to count 1s, the above works for any digit from 1 through 9. It also works for 0, if we include the leading 0s normally left out of the representation (e.g. "0001").

Now for the original problem: counting a digit d in numbers from 1 through k*10^x. Actually, let me amend this to not include k*10^x, as it's simpler to solve without and can be covered in a special case. We'll call this number pdc(k,x,d) (think "partial digit count"). Note that these two functions use x differently, as dc(x) doesn't include 10^x, whereas pdc(k,x,d) does include 10^x.

To solve this problem, we can take the same approach of figuring out how to count these digits by breaking down the numbers into patterns. If d<k, there are basically the same two cases: «d»0* .. «d»9* and 0«0*»..(k-1)«9*». However, the number of d this time is 10^x, and each «0*»..«9*» is dc(x), for a total of 10^x+k*dc(x). If d≥k, then there are no numbers with leading ds in the range, so there are only the 0«0*»..(k-1)«9*» to count. If you want to include k*10^x in the range, the only change you need to make is when d=k, in which case there's an additional d to count, or when d=0, if you want to allow counting 0s (which I won't bother with).

                  («d»0* .. «d»9*)       (0«0*» .. (k-1)«9*»)
pdc(k,x,d), d<k =    10 ^ x           +     k * dc(x)
                = 10 ^ x  + k * x * 10^(x-1)
                = (10 + k * x) * 10^(x-1)
                
                  (0«0*» .. (k-1)«9*»)
pdc(k,x,d), d>k =  k * dc(x)
               = k * x * 10^(x-1)
pdc(k,x,d), d=k = 1+k * x * 10^(x-1)

Final C function:

long count_digits_from_range(k,x,d) {
    if (d < k) {
        return (10 + k*x) * pow(10,x-1);
    } else if (d==k) {
        return 1 + k * x * pow(10,x-1);
    } else {
        return k * x * pow(10,x-1);
    }
}

Time: 1.55 µs unoptimized, compared to 24s optimized (-O3) for the original, which is a speedup of over 1.5e7 times faster.

Addendum: 5e8 isn't the only fixed point. From the formula in pdc, we can get fixed points whenever d<k and (10+k*x)*10^(x-1) = k*10^x, or d>k (d≥k, if we don't include k*10^x) and k*10^x=k*x*10^(x-1), where 0 < k < 10. The former is equivalent to x=10(k-1)/k, which leads to the solutions (k,x) in [(1, 0), (2, 5), (5, 8)] when d<k:

# Python
>>> [(k,int(x)) for k,x in [(k, 10.0*(k-1.0)/k) for k in range(1,10)] if int(x)==x]
[(1, 0), (2, 5), (5, 8)]

The latter is much simpler to solve: 10=x when d>k, giving fixed points of 1e10, 2e10, ... 8e10. 9e10 is a fixed point if k*10^x isn't included in the count.