Numbers that contain a 1

How can i find qt. numbers includes a 1 in the segment [1..n]? eg: for n=29 it is 12; for n=100 it is 20. n can reach 10^9 and time limit is 2 se开发者_如何学Goc. language C++

A simple way to check if a single number is to compute its modulo 10: if it's 1 then it does, otherwise divide it by 10 and repeat. If the number is 0, it doesn't include 1.

That should be enough for you to start.

Clever thing to do is create a formula, prove it by recursion, then apply it.

Actually I will not use recursion at first but some simple maths: sort of probability/combinatorial theory although there are no random events here.

Given a number of digits say two, the number of numbers below that do not have any 1s is always going to be 9 to the power of the number of digits, thus for 00 to 99 the are 81 such numbers. Thus there are 19 that do (100-81).

In each case we will count the number of numbers that do not contain any ones.

5394 for example is the sum of the range 0 to 4999 and the sum of the range 5000 to 5394.

Sum to 4999 is the product of the digits: 4*9*9*9 (0-4, 0-9, 0-9, 0-9 excluding 1 in each case)

Sum 5000 to 5394 is the same as the sum from 000 to 394: split 000 to 299, 300 to 394. Thus 2*9*9 + run from 00 to 94 which is 8*9 plus 90-94 which is 4 more.

So from 0 to 5394 there are 4*9*9*9 (2916) + 2*9*9 (162) + 8*9 (72) + 4 = 3154

Subtract from our main number+1 (5395) and we get the solution of 2241. (We subtract from 5395 because we counted from 0 to 5394, which is 5395 numbers)

Solution is take each digit that is >1, subtract one, and multiply by 9 for each digit that appears after it. If the number is 1 we do not subtract one. If the number is zero we skip.

If we encounter a 1 we skip all the remaining digits. Thus if our number is 52136, after reaching the 1 we skip all the rest. (We will have the count up to 52099 and there are no more after that). We still use the whole number for the subtraction at the end.

For the last digit: If there have been no 1 digits so far we add the last digit in, and add 1 if it is 0. Thus add 4 for 5394, 1 for 5390, nothing for 5216 because it contains a 1 before the last digit but still add 1 for 5391 (representing 5390 that wasn't include in the earlier count).

Then subtract this sum from our number+1 and subtract 1 more (because I have ranged 0 to N which is N+1 numbers)

n=29 is thus 1*9 + 9 = 18. Subtract from n+1 and we get 12 like you wanted.

n=100: 1*9*9 = 81. Subtract from 101 (our number contains a 1) to get 20.

There is your formula. Now go and program it.

** Slightly alternative way **

In a "recursive" way: We calculate the number of numbers that do not contain a 1 strictly less than our value (not including it) let's call this a name, f(N)

f(10N) is always f(N) * 9. We can prove this easily: there are f(N) numbers that are less than N then multiply these by 10 and add in each of the digits 0 and 2-9 at the end, 9 different digits.

f(10N+m) where 0<=m<=9 is a single digit uses the "last digit add" formula so if N contains a 1 digit it is just f(N) * 9 otherwise add 0 for m=0 1 for m=1 and m-1 for any other.

f(394858) = 7 + 9*f(39485) f(573940) = 9*f(57394) f(491029) = 9*f(49102) (contains a 1 digit)

Your "f" function can recurse and must contain 2 pieces of information: whether it contains a 1 digit and the return value. The base case is single digit

f(N) is the number of numbers strictly less than N that do not contain a 1. To get the number that do, subtract this from N, and add 1 if our number itself contains a 1.

f(10N+M) = 9*f(N) if N contains a 1, 9*f(N)+f(M) if N does not contain a 1.

f(0) = 0 f(1) = 1 f(M) for 2 to 9 is M-1 f(10) = 9 * f(1) = 9 f(100) = 9 * f(10) = 81 solution is 100 - 81 + 1 (because 100 contains a 1 we add one) which gives us 20 f(9) = 8 f(99) = 8*9 + 8 = 80 subtract 80 from 99 to give us 19 and do not add 1 as 99 does not contain a 1. Now let's try coding:

struct res 
{
  unsigned int numDigs;
  bool hasOneDig;

  res( unsigned int n, bool h ) : numDigs( n ), hasOneDig( h ) {}
};

res oneDigitCount( unsigned int input )
{
   assert( input < 10 );

   switch( input )
   {
      case 0: 
         return res( 0, false );
      case 1:
         return res( 1, true );
      default:
         return res( input-1, false );
   }
};

res countNoOnes( unsigned int input )
{
   if( input < 10 )
        return oneDigitCount( input ); // base case that ends recursion

   unsigned int quotient = input / 10;
   unsigned int remainder = input % 10;

   res result = countNoOnes( quotient ); // recursive
   result.numDigs *= 9;

   if( !result.hasOneDig )
   {
       res remainderRes = oneDigitCount( remainder );
       result.numDigs += remainderRes.numDigs;
       if( remainderRes.hasOneDig ) // or remainder==1
          result.hasOneDig = true;
   }

   return result;
}

unsigned int countNumsContainingOne( unsigned int input )
{
   res noOnes = countNoOnes(input);
   unsigned int result = input - noOnes.numDigs;
   if(noOnes.hasOneDig)
     ++result; // as this number has a one

   return result;
}

Not very OO, could easily be adapted for C (replace constructor with function that returns the struct) but should work.

For each number, do this: create outer loop for all the numbers from 1 to n.

You can printf() it to a string buffer (char[10] for example), then check the same string buffer if contains '1' with simple while loop.

I'll leave the implementation to you :)

Since it's tagged homework, I won't give you the C++ code since you should do some of the work :-)

You can break it down into two problems, the first one being how to tell if a given number contains a one. This has an elegant recursive solution:

def containsOne (n):
    if n <= 0:
        return 0
    if n % 10 == 1:
        return 1
    return containsOne (n / 10)

This will return 0 for any number zero or less and return 1 if it contains a 1. It does this by recursively checking the least significant digit for a 1. If it is, it returns 1 otherwise it divides the number by 10 (integer division like 472 becoming 47) and continues.

Then you have a simple iterative function for counting:

def countOfOneNumbersOneTo(n):
    count = 0
    for i = 1 to n:
        count = count + containsOne(i)
    return count

That's about the simplest code that'll do the trick.

You can see it in action in the following Python code (which is about as close to pseudo-code as a language gets):

import sys

def containsOne (n):
    if n <= 0:
        return 0
    if n % 10 == 1:
        return 1
    return containsOne (n / 10)

def countOfOneNumbersOneTo(n):
    count = 0
    for i in range(1,n+1):
        count = count + containsOne(i)
    return count

print countOfOneNumbersOneTo (int (sys.argv[1]))

and transcript:

$ python qq.py -10
0

$ python qq.py 0
0

$ python qq.py 1
1

$ python qq.py 9
1

$ python qq.py 10
2

$ python qq.py 29
12

$ python qq.py 100
20

A C version follows:

#include <stdio.h>
#include <stdlib.h>

static int containsOne (int n) {
    if (n <= 0)
        return 0;
    if (n % 10 == 1)
        return 1;
    return containsOne (n / 10);
}

static int countOfOneNumbersOneTo (int n) {
    int i, count = 0;
    for (i = 1; i <= n; i++)
        count = count + containsOne(i);
    return count;
}

int main (int argc, char *argv[]) {
    printf ("%d\n", countOfOneNumbersOneTo (atoi (argv[1])));
    return 0;
}

If you want raw speed, one option is to pre-calculate all values and write the results to a file. The initial process will be a little slow but, once you have the values written to a fixed-length-record file, the lookup is a simple, relatively fast, seek/read operation.

For the number 10⁹, this takes a little over 8 minutes to do on my old clunker laptop and you need to remember that you don't need to do this for every number since, once you've established that 100 has 20 results, you just have to check 101 and add 1 (since 101 has a 1) to the 20. Similarly, knowing that 1999999 has 1468559 results, check 2000000 and add 0 (since it has no 1's).

I've actually used this trick before with a file containing millions and millions of primes. Turning this into a bitmask in a file, I have an isPrime() method that blows most any calculating variant out of the water :-)