[algogeeks] Re: Divisibility by five

@Dave: I hate to reply to myself, but I should have tested a few more cases, as the code doesn't work for k that is a power of 2, and other cases. Sorry. Dave On Jan 22, 12:54 pm, Dave wrote: > @Gene & Lucifer: Great thinking. For binary integers, you can > calculate the states of the finite aut

[algogeeks] Re: Divisibility by five

@Gene & Lucifer: Great thinking. For binary integers, you can calculate the states of the finite automaton as you go, without ever storing it. The following code returns true if and only if the arbitrary integer n is divisible by the arbitrary nonzero integer k. int IsDivisibleBy( int n, int k ) /

[algogeeks] Re: Divisibility by five

You can extend this thinking to finding the value mod M of any string of base B digits. (In this case M=5, B=2, and you are looking for a mod 5 value of zero.) Construct a finite automaton with M states 0 to M-1. The current state of the automaton tells you the value mod M of the digits seen so f

[algogeeks] Re: Divisibility by five

@above... The above explanation is based on the answer that i gave to the following question asked: Given an infinite stream of bits, at any given point of time u have tell whether the no. formed by the bits sent till now is divisible by 3. The catch in the above question is that you can't store

[algogeeks] Re: Divisibility by five

@another approach.. The remainders when the following nos. are divided by 5 are : Numbers Remainder 2^01 2^12 2^24 (-1) 2^33 (-2) Now, we know that given a product of nos. a1, a2, ... aN when

[algogeeks] Re: Divisibility by five

@Arun: Proof that n = 4*a + b is a multiple of 5 if and only if a - b is a multiple of 5: Given n, write it as n = 4*a + b where 0 <= b <= 3. Note that 5*a is a multiple of 5, and 5*a - n = 5*a - (4*a + b) = a - b. If n is a multiple of 5, then 5*a - n is a multiple of 5, so a - b is a multiple of

[algogeeks] Re: Divisibility by five

@Arun: Some time ago, there was a question about determining divisibility by 3. I thought about determining divisibility of decimal numbers by 9 using the "casting out nines" procedure: sum the decimal digits of the number; the number is divisible by 9 if the sum of the digits is divisible by 9. Ca

[algogeeks] Re: Divisibility by five

@Karthikeyan: Again I ask: Do you think that you have used neither division nor mod indirectly? I.e., can you assert with certainty that there is no division or mod in sprintf() or anything it calls? I didn't think so. In fact, I am willing to assert with certainty that division is used, since the

Re: [algogeeks] Re: Divisibility by five

@dave: thanks for that..but i just wanted to know as to how u thot of converting n to a-b in the iteration. when u say 4a +b is a multiple of 5 iff a-b is a muliple of 5 i was able to get that only when i tried an example...if they ask divisbility by 3 or 6 or 7 how wud the logic change?? On Sat,

Re: [algogeeks] Re: Divisibility by five

check the last char ... it should be 0 or 5 , int to string without mod On Sat, Jan 21, 2012 at 10:05 PM, Dave wrote: > @Karthikeyan: Is this supposed to relate to the question of > determining divisibility by 5? > > Dave > > On Jan 21, 9:25 am, karthikeyan muthu > wrote: > > @dave > > > > int

[algogeeks] Re: Divisibility by five

@Karthikeyan: Is this supposed to relate to the question of determining divisibility by 5? Dave On Jan 21, 9:25 am, karthikeyan muthu wrote: > @dave > > int no=10; > char ans[100]; > sprintf(ans,"%d",no); > cout< > On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan > wrote: > > > > > @dave or a

[algogeeks] Re: Divisibility by five

@Arun: (n & 3) is the bitwise logical product of the integer n and the binary number 0...0011. The result simply is the two low-order bits of n. I.e., if n = 0...011100110 in binary, then (n & 3) is 0...010 in binary, because the two lowest order bits of n are 1 and 0. There is an explanation of w

Re: [algogeeks] Re: Divisibility by five

@dave int no=10; char ans[100]; sprintf(ans,"%d",no); cout @dave or anyone: can u pls explain the logic of n&3 in dave's solution? > why is it subtracted from n(which is divided by 4 using >>2) and what does > n& 3 indicate? > > > On Sat, May 7, 2011 at 9:38 AM, Dave wrote: > >> @Umer:

Re: [algogeeks] Re: Divisibility by five

@dave or anyone: can u pls explain the logic of n&3 in dave's solution? why is it subtracted from n(which is divided by 4 using >>2) and what does n& 3 indicate? On Sat, May 7, 2011 at 9:38 AM, Dave wrote: > @Umer: Do you suppose that you can convert an int into a string > without using division

[algogeeks] Re: Divisibility by five

@Umer: Do you suppose that you can convert an int into a string without using division or mod, either directly or indirectly? Dave On May 4, 1:12 am, Umer Farooq wrote: > I'm surprised to see that why are you guys making this problem so complex. > This problem can be solved in two steps only. >

Re: [algogeeks] Re: Divisibility by five

I'm surprised to see that why are you guys making this problem so complex. This problem can be solved in two steps only. 1- Convert the given int into string 2- Check if the last character is 0 or 5. // it yes, then return true else return false for e.g. 125 (last character is 5 ... therefore it

[algogeeks] Re: Divisibility by five

@anshu: Spoiler alert... I was thinking of something more along the line int DivisibleBy5 (int n) { n = n > 0 ? n : -n; while( n > 0 ) n = (n >> 2) - (n & 3); return (n == 0); } To see that it works, write n as n = 4*a + b, where 0 <= b <= 3. Then the iteration replaces n by a

Re: [algogeeks] Re: Divisibility by five

awesome solution On Tue, May 3, 2011 at 1:43 PM, anshu wrote: > algorithm: > > if any number(a) is divisible by 5 it can be wriiten as 4*b + b --> > this cleary shows the last two bit of a & b will be same. > > lets understand by an example (35)10 = (100011)2 > > xx1100 > + xx11 > - >

[algogeeks] Re: Divisibility by five

algorithm: if any number(a) is divisible by 5 it can be wriiten as 4*b + b --> this cleary shows the last two bit of a & b will be same. lets understand by an example (35)10 = (100011)2 xx1100 + xx11 - 100011 now this clearly shows we can calculate the unknowns(x) by traversing righ

Re: [algogeeks] Re: Divisibility by five

Given it should be of O(log(n)). On Tue, May 3, 2011 at 12:48 PM, abhishekriyer wrote: > A naive method would be repeated subtraction which is division. So > subtract the number repeatedly by 5 unless the value that remains is > less than 0. If its 0 then the number is divisible by 5 > > On May 3

[algogeeks] Re: Divisibility by five

A naive method would be repeated subtraction which is division. So subtract the number repeatedly by 5 unless the value that remains is less than 0. If its 0 then the number is divisible by 5 On May 3, 9:25 am, Dave wrote: > Given an integer n, give an O(log n) algorithm to determine if n is > di

[algogeeks] Re: Divisibility by five

http://www.ken.duisenberg.com/potw/archive/arch05/050608sol.html On May 3, 9:25 am, Dave wrote: > Given an integer n, give an O(log n) algorithm to determine if n is > divisible by 5 without using division or mod. -- You received this message because you are subscribed to the Google Groups "Al