Check divisibility by 3

[richa gupta]

can we check the divisibility of a given number by 3 withoutusing
operators like '/' or '%'.
I want the efficient solution to this problem ..

can someone help ??
--
Richa Gupta
(IT-BHU,India)

[vinod gupta]

Keep subtracting 3 from the given number until you get a number less than 3 and greater or equal to 0.
count the number of times you subtracted 3 from it. That would be your quotient and number you get in the last would be your remainder.

Similarly you can go for other way round.Instead of subtracting you can check the number if it is less than 3 return it as remainder and 0 as quotient. Else start from 0 and keep on adding 3 until difference becomes 0,1,2.

There is another method too which deals with bit and which is the most efficient.

Thanks
Vinod

[Kannan Ekanath]

"Keep subtracting 3 from the given number until you get a number less than 3"

This can be made faster by just adding the digits in a given number (which will be a multiple of 3, if the original number was) and then proceeding with that number :)

Am not sure if that is the fastest though :)

2009/8/14 vinod gupta <vino...@gmail.com>

--
Regards,
Kannan Ekanath

[vinod gupta]

How would you add the digit? The problem is how would you get the individual digits without using % and / operator?

Fastest method is using bitwise manipulation that is a bit tricky.

Thanks
Vinod

[CH Gowri Kumar - గౌరీ కుమార్]

Let me give an hint:

The decimal equivalent of a binary representation of number  abcdef is
(where all a,b,c,d,e,f are either zero or 1):

2^0 * f + (2^1) * e + (2^2) * d + (2^3) *c + .....
(Note : ^ is used to denote power (and not xor)

Now replace 2 by 3-1 in the above representation
(3-1)^0 *f + ((3-1)^1)*e + ((3-2)^2)*d + ....

Applying binomial theorm, we can notice that each of the every term of
the expansion (3-1)^n will have a 3 except the last term, which would
either be a 1 or -1 depending on the value of n.

We can use this observation as follows:
- Get every bit in the number
- check if it is  1
- If so, add -1 or 1 depending on the position of the bit.

If the resutant sum is divisible by 3, then the original number is
divisible by 3.

Regards,
Gowri Kumar

[richa gupta]

Hi,

I am extremely sorry. The above question was not complete. It is

can we check the divisibility of a given number by 3 withoutusing

operators like '/' or '%'. You have given itoa( ) function.

 I want the efficient solution to this problem ..

can someone help ??

2009/8/14 Arun N <arun...@gmail.com>

take an number find its binary
add all odd bits and even bits seperately
now check if the difference is divisible by 3
if yes it is
say 6 110  ----->  1+0 - 1 =0
9 1001 -----> 1+0 - 0+1 = 0
12 1100  ------> 1+0 - 1+0  = 0
Arun,

On Fri, Aug 14, 2009 at 1:15 PM, richa gupta <richa...@gmail.com> wrote:

--
Potential is not what U have, its what U think U have!!!
It is better to worn out than rust.

--
Richa Gupta
(IT-BHU,India)

[richa gupta]

I got the solution :)

using itoa() we can get the digits of a number.algo is :

 

1. add the digits of the number and store the sum in result.

2. if result > 10 { got to step 1 ; }

3. if result is 3 , 6 or 9 then number wil be divisible by3

  else it wil nt be divisible by 3 

[Sridhar Jammalamadaka]

Nice problem and nice solution Richa!

-Sridhar

richa gupta wrote:
> I got the solution :)
>
> using itoa() we can get the digits of a number.algo is :
>
> 1. add the digits of the number and store the sum in result.
> 2. if result > 10 { got to step 1 ; }
> 3. if result is 3 , 6 or 9 then number wil be divisible by3
> else it wil nt be divisible by 3
>
>

> On 2009-08-14, *CH Gowri Kumar - గౌరీ కుమార్* <gkum...@gmail.com

[Dave]

Given a value of n,

for( i = iabs(n) + 3 ; i > 3 ; i = ( i & 3 ) + ( i >> 2 ) );

After the above loop, if i == 3, then n is a multiple of 3, otherwise
n is not a multiple of 3. This simply is a "casting out of threes"
algorithm.

Dave