Wednesday, July 23, 2008

Find whether a number is divisible by 3 or not

Given an array of bits, find out whether the number represented by the binary number is divisible by 3 or not.

If the difference of the no.of 1's in even position and odd position is divisible by 3, then the no.is divisible by 3.

For example, for 18, the binary number is 10010. We can count either from left or right. That will not make any difference. If we count from left, there is one 1 in odd position, and one 1 in even position. The difference is Zero, which is divisible by 3. So, the number 10010 is divisible by 3.

If we take the number 37, the binary number is 100101. The number of 1's in odd position is 1, and the no.of 1's in even position is 2. The difference is 1, and it is not divisible by 3. So, 37 is not divisible by 3.


// Returns non-zero number, if it is divisible. Zero, otherwise.
int divisible(int array[], int n)
{
int i, even=0, odd=0;
for(int i=0; i < n; i++) {
if(array[i]==1) {
if(i%2==0)
even++;
else
odd++;
}
}
return ((even-odd)%3==0);
}

1 comment:

  1. if sum of all decimal digits is divisible by 3 then the given number is divisible by 3

    ReplyDelete