CODEWITHSUNDEEP
c
Rohit
Rohit

Reputation: 7161

Check to see if integer is one in which each digit is either a zero or a one

What is the efficient way in C program to check if integer is one in which each digit is either a zero or a one ?

example 100 // is correct as it contains only 0 or 1

701 // is wrong

I tried for 

    int containsZero(int num) {
        if(num == 0)
            return 0;

        if(num < 0)
            num = -num;

        while(num > 0) {
            if(num % 10 == 0)
                return 0;
            num /= 10;
        }
        return -1;
    }

int containsOne(int num) {
    if(num == 0)
        return 0;

    if(num < 0)
        num = -num;

    while(num > 0) {
        if(num % 10 == 1)
            return 0;
        num /= 10;
    }
    return -1;
}

Upvotes: 0

Views: 2759

Answers (5)

ShinTakezou
ShinTakezou

Reputation: 9681

Preamble

Good straightforward algorithms shown in other answer are O(n), being n the number for the digits. Since n is small (even using 64bit integer we won't have more than 20 digits), implementing a "better" algorithm should be pondered, and meaning of "efficient" argued; given O(n) algorithms can be considered efficient.

"Solution"

We can think about sparse array since among 4 billions of numbers, only 2^9 (two symbols, 9 "positions") have the wanted property. I felt that some kind of pattern should emerge from bits, and so there could be a solution exploiting this. So, I've dumped all decimal numbers containing only 0 and 1 in hex, noticed a pattern and implemented the simplest code exploiting it — further improvements are surely possible, e.g. the "table" can be halved considering that if x is even and has the property, then x+1 has the property too.

The check is only

bool only01(uint32_t n)
{
    uint32_t i = n & 0xff;
    uint32_t r = n >> 8;
    return map01[i][0] == r || map01[i][1] == r;
}

The full table (map01) and the test code are available at this gist.

Timing

A run of the test ("search" for numbers having the property between 0 and 2 billions — no reason to go beyond) with my solution, using time and redirecting output to /dev/null:

real    0m4.031s
user    0m3.948s

A run of the same test with another solution, picked from another answer:

real    0m15.530s
user    0m15.221s

Upvotes: 1

stefan
stefan

Reputation: 10355

Well, in the worst case you have to check every digit, so you cannot have an algorithm better than O(d), where d is the number of digits.

The straight-forward approach satisfies this:

int n = 701;
while ( n != 0 && (n % 10) <= 1 )
{
   n /= 10;
}
if ( (n % 10) > 1 )
{
    printf("Bad number\n");
}
else
{
    printf("Good number\n");
}

This assumes positive numbers though. To put it into a general function:

int tester(int n)
{
   if ( n < 0 )
   {
       n = -n;
   }
   while ( n != 0 && (n % 10) <= 1 )
   {
      n /= 10;
   }
   return ( (n % 10) <= 1 );
}

Demo: http://ideone.com/jWyLdl

What are we doing here? We check if the last decimal digit (n % 10) is either 0 or 1, then cut of the last digit by dividing by ten until the number is 0.

Now of course there is also another approach. If you are guaranteed to have e.g. always 32bit integers, a look-up table isn't that large. I think it may be around 2048 entries, so really not that big.

You basically list all valid numbers: 0 1 10 11 100 101 110 111 ...

Now you simply search through the list (a binary search is possible, if the list is sorted!). The complexity with linear search would be, of course, worse than the approach above. I suspect binary search beeing still worse in actual performance, as you need to jump a lot in memory rather than just operating on one number.

Anything fancy for such a small problem is most probably overkill.

Upvotes: 2

invalid_id
invalid_id

Reputation: 804

You can peel of every digit and check it. This takes O(n) operations.

int input;
while (input != 0)
{
  int digit = input %10; //get last digit using modulo
  input = input / 10; //removes last digit using div
  if (digit != 0 && digit != 1)
  {
     return FALSE;
  }
}
return TRUE;

Upvotes: 2

MByD
MByD

Reputation: 137392

You work with base 10, so, each time check the % 10:

int justOnesAndZeros(int num) {
    while ( num )
    {
        if ( ( num % 10 != 1 ) && ( num % 10 != 0 ) )
        {
            return FALSE;
        }
        num /= 10;
    }
    return TRUE;
}

Upvotes: 0

Aswin Murugesh
Aswin Murugesh

Reputation: 11070

The best solution I can think of, without using strings:

while(n)
{
    x = n%10;
    if(x>1)
        return -1;
    n /= 10;
}
return 0;

Upvotes: 1

Related Questions