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 + 99cis divisible by 3. So if

a + b + c + dis 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: C

## About this entry

You’re currently reading “

- Published:
- 4:04 AM
- by Anoob Backer

## 7 Comments (Post a Comment)