In step 3, if n > m, then n can be written in the form i * 2^k + j,
where i > 0 and 0 <= j <= m. Then, step 3 replaces n by i + j. Note
that
(i * 2^k + j) - (i + j) = i * (2^k - 1) = i * m.
Therefore, the step replaces any number greater than m by a small
number that differs from it by a multiple o
@Dave Logic is good.
could not understand how does it works. Could you please explain
On Tue, Jun 22, 2010 at 9:16 PM, Dave wrote:
> Let m = 2^k - 1.
> To check divisibility of n by m,
> 1. If n is zero, return true.
> 2. If n is negative, replace n with -n.
> 3. While n > m, replace n with (n
Let m = 2^k - 1.
To check divisibility of n by m,
1. If n is zero, return true.
2. If n is negative, replace n with -n.
3. While n > m, replace n with (n >> k) + (n & m).
4. Return (n == m).
This is equivalent to the "casting out nines" algorithm to determine
if a number is a multiple of 9.
Dave
nice logic and to add simple too!!
--
Abhijeet
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group,
Richa,
Did you see http://geeksforgeeks.org/?p=511
I think, above link provides the kind of solution you are looking for
On Thu, Aug 20, 2009 at 11:33 PM, Ralph Boland wrote:
>
>
>
> On Aug 16, 7:29 pm, Ralph Boland wrote:
> > On Aug 14, 1:45 am, richa gupta wrote:
> >
> > > can we check the
On Aug 16, 7:29 pm, Ralph Boland wrote:
> On Aug 14, 1:45 am, richa gupta wrote:
>
> > 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-
I think my solution, posted on August 16, but repeated here for ease
of reference, is a more efficient... the body of the loop is simpler
and the procedure does not use recursion.
Given a value of n,
for( i = iabs(n) + 3 ; i > 3 ; i = ( i & 3 ) + ( i >> 2 ) );
After the above loop, if i == 3, t
This is solved and very well explained at http://geeksforgeeks.org/?p=511
On Aug 17, 7:19 am, Abhijeet Kumar wrote:
> i think the code given above doesn't work ..
> so may be dat needs to be checked
> any better ideas??
>
>
>
> On Mon, Aug 17, 2009 at 7:20 PM, manish bhatia wrote:
> > Keep
i think the code given above doesn't work ..
so may be dat needs to be checked
any better ideas??
On Mon, Aug 17, 2009 at 7:20 PM, manish bhatia wrote:
> Keep adding the digits till you are reduced to single digit. Then check if
> it is 3, 6 or 9
>
> --
> *From:
Keep adding the digits till you are reduced to single digit. Then check if it
is 3, 6 or 9
From: richa gupta
To: programming-puzzles ; algogeeks
Sent: Friday, 14 August, 2009 1:15:13 PM
Subject: [algogeeks] Check divisibility by 3
can we check the divisibi
#include
int main() {
int num,tmp=1;
printf("Enter the number \n");
scanf("%d",&num);
while(num>9) {
while(num>tmp)
tmp=tmp<<1;
tmp>>1;
num=num-tmp;
tmp=1;
}
if(num==9 || num==6 || num==3)
printf("\nNumber divisible by 3
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
On Aug 14, 2:45 am, richa gupta wrote:
> can we check the d
On Aug 14, 1:45 am, richa gupta wrote:
> 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)
If the number is an arbitrarily large binary num
10101010 = 170
On Fri, Aug 14, 2009 at 8:04 PM, sharad kumar wrote:
> boss will ur code work for 330 in binary 10101010??
>
> On Fri, Aug 14, 2009 at 3:09 PM, Arun N wrote:
>
>> take an number find its binary
>> add all odd bits and even bits seperately
>> now check if the difference is divisibl
Can u pls elaborate on what is the given iota( )?
On Fri, Aug 14, 2009 at 7:11 PM, richa gupta wrote:
>
> 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(
boss will ur code work for 330 in binary 10101010??
On Fri, Aug 14, 2009 at 3:09 PM, Arun N wrote:
> 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
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
> take an num
i think itoa wont work for long long type and as far i know it is designed
to work only for integers only... so u cant find remainder for longer
numbers with the logic u said above
On Fri, Aug 14, 2009 at 7:36 PM, sharad kumar wrote:
> say withou itoa yaar.
>
>
> On Fri, Aug 14, 2009 at 7:35 PM
say withou itoa yaar.
On Fri, Aug 14, 2009 at 7:35 PM, Yogesh Aggarwal <
yogesh.aggarwa...@gmail.com> wrote:
> u can use the itoa function for that...
>
>
> On Fri, Aug 14, 2009 at 7:31 PM, sharad kumar wrote:
>
>> brother how do u get the digits of number ???u use % and / rite??
>>
>>
>> On Fri,
u can use the itoa function for that...
On Fri, Aug 14, 2009 at 7:31 PM, sharad kumar wrote:
> brother how do u get the digits of number ???u use % and / rite??
>
>
> On Fri, Aug 14, 2009 at 7:28 PM, Yogesh Aggarwal <
> yogesh.aggarwa...@gmail.com> wrote:
>
>> (CORRECTED ALGO.)
>> We can do like
brother how do u get the digits of number ???u use % and / rite??
On Fri, Aug 14, 2009 at 7:28 PM, Yogesh Aggarwal <
yogesh.aggarwa...@gmail.com> wrote:
> (CORRECTED ALGO.)
> We can do like dis...
> - add all d digits of the no.
> - if the result is MORE than 10, add all the digits of the result
(CORRECTED ALGO.)
We can do like dis...
- add all d digits of the no.
- if the result is MORE than 10, add all the digits of the result again.
- continue step2 if the result is still MORE than 10
- if the result is either 0, 3 , 6 or 9 den the no. is divisible by 3.
example 1 :
num = 12345
sum1 =
(CORRECTED ALGO.)
We can do like dis...
- add all d digits of the no.
- if the result is MORE than 10, add all the digits of the result again.
- continue step2 if the result is still less than 10
- if the result is either 0, 3 , 6 or 9 den the no. is divisible by 3.
example 1 :
num = 12345
sum1 =
given a number n
u can get the quotient when it is divided by 4 using right shift 2 times
like n >> 2 this ll give u quotient(q)
u can get the remainder by subtracting 4 * q from n which will give the
remainder when divided by 4
by doing this u ll express n as n = 4q + r = 3q + (q+r)
in this al
Just substract 3 till grater than 2 if you end with 0 it is divisible
othervise not, or you can binary search the result
division by 2 is just shift.
2009/8/14 Yogesh Aggarwal
> @arun : we are not supposed to use / operator. but in ur algo u r using /
> or % has to be used to check wether the
@arun : we are not supposed to use / operator. but in ur algo u r using / or
% has to be used to check wether the diff is divisible by 3.
We can do like dis...
- add all d digits of the no.
- if the result is less than 10, add all the digits of the result again.
- continue step2 if the result is s
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 wrote:
>
> can we check
i think use of shift operator can do d job
On Fri, Aug 14, 2009 at 1:15 PM, richa gupta wrote:
>
> 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-BH
28 matches
Mail list logo
