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, then n is a multiple of 3, otherwise n is not a multiple of 3. If your complaint is that it is not well explained, then note that the expression ( i & 3 ) + ( i >> 2 ) separates i into two parts, ( i & 3 ), which equals the lower-order 2 bits of i, and int( i/4 ), which equals ( i >> 2 ), the upper bits of i. Note that i = ( i & 3 ) + 4 * int( i/4 ) = ( i & 3 ) + int( i/4 ) + 3 * int( i/4 ) = ( i & 3 ) + ( i >> 2 ) + 3 * int( i/4 ) = ( i & 3 ) + ( i >> 2 ) + a multiple of 3. Furthermore, note that if i > 3, then int( i/4 ) > 0, so ( i & 3 ) + ( i >> 2 ) < i, and if i > 0 then ( i & 3 ) + ( i >> 2 ) > 0. Thus, i is reduced on each iteration of the loop, and since there are only finitely many integers between the original value of i and 3, eventually, i must be reduced to an integer 1 <= i <= 3. Since each reduction is by a multiple of three, if the original i is a multiple of three, then the loop exits with i = 3, but if the original i is not a multiple of three, then the loop exits with i = 1 or i = 2. Dave On Aug 19, 10:39 am, sandy <[email protected]> wrote: > This is solved and very well explained athttp://geeksforgeeks.org/?p=511 > > On Aug 17, 7:19 am, Abhijeet Kumar <[email protected]> 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 <[email protected]> wrote: > > > Keep adding the digits till you are reduced to single digit. Then check if > > > it is 3, 6 or 9 > > > > ------------------------------ > > > *From:* richa gupta <[email protected]> > > > *To:* programming-puzzles <[email protected]>; > > > algogeeks <[email protected]> > > > *Sent:* Friday, 14 August, 2009 1:15:13 PM > > > *Subject:* [algogeeks] Check divisibility by 3 > > > > 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) > > > > ------------------------------ > > > Yahoo! recommends that you upgrade to the new and safer Internet Explorer > > > 8<http://in.rd.yahoo.com/tagline_ie8_1/*http://downloads.yahoo.com/in/i...> > > > . > > > -- > > Abhijeet- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
