C Programming - Divisible By 3 or Not

Given a number we have to find whether it is divisible by 3 or not without using /,%,*.

We are provided with char *itoa(int) function

Please post in your comments. Let us find a good solution!!!!
Solution:
One of the property of a number divisible by 3 is that its sum of digits will be also divisible by 3.
Suppose abcd is a 4 digit decimal number

abdc = 1000a + 100b + 10c + d = (999a + 99b + 9c) + (a + b + c + d)

Here the 
999a + 99b + 99c
is divisible by 3. So if 
a + b + c + d
is also divisible by three then the number is divisible by three.

Functions:

The most obvious one is

/* returns the remainder */
int mod3(unsigned number)
{
    while (number > 3 ) { number -= 3; }

    number = number == 3 ? 0 : number;
    return number;
}

The same thing modified in a bitwise form will be

int mod3(unsigned number)
{
    const unsigned int s = 2;
    const unsigned int d = (1 << s) - 1;
    unsigned int modulus;

    for (modulus = number; number > d; number = modulus) {
        for (modulus = 0; number; number >>= s) {
            modulus += number & d;
        }
    }
    modulus = modulus == d ? 0 : modulus;
    return modulus;
}

But here are we are provided with atoi so a better solution could be

int mod3(int number)
{
    char *iter;
    char *str = itoa(number);
    while( *(str+1) != '\0' ) {
       number = 0; iter = str;
       while( *iter != '\0' ) {
            number += (*iter - '0');
            iter++;
       }
       str = itoa(number);
    }
    if ( (*str == '3') || (*str == '6') || (*str == '9') )
       return 0;
    return 1;
}

The defect with this function is that if not divisible it will always return 1 rather than the modulus.

Labels:

About this entry

You’re currently reading “C Programming - Divisible By 3 or Not,” an entry on ANOOB BACKER Technical Blog

Published:
4:04 am
by -