Author |
Topic: A puzzler (Read 6925 times) |
|
u_think_u_succeed
Newbie
Gender: 
Posts: 31
|
Given a number, how can u determine using C, whether it is divisible by 3, without using *, /, % operators.
You may assume that itoa() function is available.
|
|
 IP Logged |
|
|
|
I_am_searching
Newbie
Gender:
Posts: 30
|
 |
Re: A puzzler
« Reply #1 on: Jul 22nd, 2007, 6:21am » |
 Quote  Modify
|
convert the number to the string using itoa();
add up all the digits
checkDivisibility(int num){
char *str=itoa(num)
while (1)
{
for (i =0 ; i < strlen(str);i++)
sum= sum + (str[i] - "0");
if (sum > 10)
str=itoa(sum);
else
break;
}
if(sum == 3 || sum == 6 || sum == 9)
printf("Number divisible by 3");
else
printf("Number not divisible by 3");
}
|
|
IP Logged |
|
|
|
I_am_searching
Newbie
Gender:
Posts: 30
|
|
Re: A puzzler
« Reply #2 on: Jul 22nd, 2007, 6:23am » |
Quote Modify
|
Correction....
add sum=0;
just at the beginning of while loop
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #3 on: Jul 22nd, 2007, 7:04am » |
Quote Modify
|
Doesn't seem very nice to use itoa
How about something along the lines of
Code:
if(n < 0)
n = -n;
while (n >= 3)
{
n = (n & 1) - (n & 2)>>1 + n >> 2;
}
return n==0; |
|
[edit]Added the >>1 for (n & 2) which was mistakenly left out. (Pointed out in replies 30,32)[/edit]
|
| « Last Edit: Nov 25th, 2007, 8:17am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
u_think_u_succeed
Newbie
Gender:
Posts: 31
|
|
Re: A puzzler
« Reply #4 on: Jul 22nd, 2007, 8:03am » |
Quote Modify
|
Towr,
Could you please explain the logic .. ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #5 on: Jul 22nd, 2007, 9:09am » |
Quote Modify
|
on Jul 22nd, 2007, 8:03am, u_think_u_succeed wrote:| Could you please explain the logic .. ? |
|
A rightshift by two is a divide by 4 and
1 = 1 (mod 3)
2 = -1 (mod 3)
4 = 1 (mod 3)
etc
Adding the bits alternately positive and negative can therefore be used for the divisibility test. Just like when you test for 11 in decimal. (For testing divisibility by 3 in decimal you add all digits, because 10n = 1 (mod 3) ).
And of course you can repeat this until you have a number n, 0  n < 3.
So we take Nk = a * 22 + b * 21 + c * 20, with a  0 and b,c  {0,1}
And turn it into Nk+1 = a - b + c
|
| « Last Edit: Jul 22nd, 2007, 9:15am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #6 on: Jul 22nd, 2007, 9:58am » |
Quote Modify
|
An approach based on the bit counting puzzle.
Code:
if (n < 0)
n = -n;
n = n & 00110011001100110011001100110011 + (n >> 2) & 00110011001100110011001100110011;
n = n & 00001111000011110000111100001111 + (n >> 4) & 00001111000011110000111100001111;
n = n & 00000000111111110000000011111111 + (n >> 8) & 00000000111111110000000011111111;
n = n & 00000000000000001111111111111111 + (n >> 16) & 00000000000000001111111111111111;
n = n & 3 + (n >> 2) & 3 + (n >> 4) & 3;
n = n & 1 - (n >> 1) & 1 + (n >> 2) & 1;
return n==0; |
|
First take the absolute value of n.
Then calculate the sum of digits in base 4: a base 4 number is divisible by 3 if the sum of its digits is divisible by 3. With a 32 bit integer we sum 16 digits, so we get at most a sum of 47 (*); which is contained in the last 6 bits of n. We can sum these as 3, base-4 digits again, and the result fits in 3 bits (**).
And then as final steps we checks divisibility by 3: add bit 1 and 3 and subtract bit 2, if this yield 0 we have a number divisible by 3.
(*) We could get 48 only if all bits were 1s, but that can only be for n=-1 and we take the absolute value before summing the base-4 digits.
(**) If we could get a sum of 48 at (*), we might spill into the 4th bit, but luckily that's avoided.
PS, those bitmasks should probably not be written in binary, because C might mistake them for octal instead; but for clarity's sake I think writing it as bitmasks makes sense.
|
| « Last Edit: Jul 22nd, 2007, 10:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
u_think_u_succeed
Newbie
Gender:
Posts: 31
|
|
Re: A puzzler
« Reply #7 on: Jul 22nd, 2007, 11:30am » |
Quote Modify
|
Marvellous Towr !!  
Hats off to you.
Well, if we know the size of the number a priori, then simply adding bits 0, 2,4, 6,8, ... 31 and subtracting bits 1,3,5,7,...30; and testing if the result is zero will do the trick (i.e. if the result is zero, then the number is divisible by 3).
|
| « Last Edit: Jul 22nd, 2007, 11:46am by u_think_u_succeed » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #8 on: Jul 22nd, 2007, 11:48am » |
Quote Modify
|
on Jul 22nd, 2007, 11:30am, u_think_u_succeed wrote:| Well, if we know the size of the number a priori, then simply adding bits 0, 2,4, 6,8, ... 31 and subtracting bits 1,3,5,7,...30; and testing if the result is zero will do the trick. |
|
True, but I think that that might be slower. In my second approach you do a lot of additions parallel.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
u_think_u_succeed
Newbie
Gender:
Posts: 31
|
|
Re: A puzzler
« Reply #9 on: Jul 22nd, 2007, 11:51am » |
Quote Modify
|
Any more examples of such type ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #10 on: Jul 22nd, 2007, 11:54am » |
Quote Modify
|
In general in base b :
a*bn = a (mod b-1)
and
a*bn = a (mod b+1) for even n and
a*bn = - a (mod b+1) for odd n
So for binary, you can easily do things for n = 3,5,7,9,15,17,31,33 etc.
For the other numbers it will be more work (because you're dealing with longer sequences that repeatedly 1 or alternating 1 and -1.)
[edit]switched b and n halfway through writing..[/edit]
|
| « Last Edit: Jul 22nd, 2007, 12:02pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
u_think_u_succeed
Newbie
Gender:
Posts: 31
|
|
Re: A puzzler
« Reply #11 on: Jul 22nd, 2007, 8:36pm » |
Quote Modify
|
Well, how about this extension,
given a number, you now actually need to divide that number by 3. The same constraints apply : No use of *, /, % operators. Again it may assumed that itoa() is available.
|
| « Last Edit: Jul 22nd, 2007, 8:37pm by u_think_u_succeed » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #12 on: Jul 23rd, 2007, 12:39am » |
Quote Modify
|
You could do a binary search for the largest K such that N > (K << 1 + K ).
I'm sure there's a more clever way, but I'll need to think a bit.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A puzzler
« Reply #13 on: Jul 23rd, 2007, 1:04am » |
Quote Modify
|
on Jul 22nd, 2007, 7:04am, towr wrote:
Are you sure it works for n=3?
Arhum... I must have been posting random text by mistake while cleaning my keyboard... 
This being said, the alternate bit count solution is nice.
|
| « Last Edit: Jul 23rd, 2007, 5:38am by Grimbal » |
IP Logged |
|
|
|
u_think_u_succeed
Newbie
Gender:
Posts: 31
|
|
Re: A puzzler
« Reply #15 on: Jul 23rd, 2007, 2:21am » |
Quote Modify
|
Quote:| You could do a binary search for the largest K such that N > (K << 1 + K ). |
|
I doubt I understand the above, but binary search anyway might involve some use of / operator.
Do you have any solution (even if it runs in linear time in number of bits) in mind ?
|
| « Last Edit: Jul 23rd, 2007, 2:22am by u_think_u_succeed » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #16 on: Jul 23rd, 2007, 2:29am » |
Quote Modify
|
on Jul 22nd, 2007, 8:36pm, u_think_u_succeed wrote:Well, how about this extension,
given a number, you now actually need to divide that number by 3. The same constraints apply : No use of *, /, % operators. Again it may assumed that itoa() is available. |
|
I think this should work:
[edit v2]Fixed the function to handle negative n. There is some choice whether you want -2 div 3 to be 0 or -1, I choose the latter.[/edit]
Code:int div3(int n)
{
if (n < 0)
return -div3(2-n);
n += 1;
n += (n >> 2);
n += (n >> 4);
n += (n >> 8);
n += (n >> 16);
n >>= 2;
return n;
}
|
|
Rationale: multiply by 1/3 = 0.01010101.. (binary)
step 1 = 1.01 N
step 2 = 1.010101 N
step 3 = 1.01010101010101 N
step 4 = 1.010101010101010101010101010101 N
step 5 = 0.01010101010101010101010101010101 N
[edit]Some frantic editing was needed because I had the wrong order (I had the final 2-right-shift at the top, which yielded wrong answer; this should now be fixed. And hopefully the rest of the reasoning is now correct.[/edit]
You need to add one if N is divisible by 3, because the binary expansion of 1/3 continues infinitely, so you alway have less than 1/3 N in step 5 (which is only a problem if N is divisible by 3, becuase its an integer divide and in the other two cases the difference is the rest value)
[edit v2]Adding 1 at the start is more effective[/edit]
It seems actually dividing by three might yield a more efficient divisibility test than the earlier approaches.
[edit v2]Just test with k=div3(n) whether (k+ k<<1) == n [/edit]
|
| « Last Edit: Jul 23rd, 2007, 3:34am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #17 on: Jul 23rd, 2007, 2:30am » |
Quote Modify
|
on Jul 23rd, 2007, 2:21am, u_think_u_succeed wrote:| I doubt I understand the above, but binary search anyway might involve some use of / operator. |
|
No, you'd just use shifting and adding.
Quote:| Do you have any solution (even if it runs in linear time in number of bits) in mind ? |
|
Yup, just now 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
I_am_searching
Newbie
Gender:
Posts: 30
|
|
Re: A puzzler
« Reply #18 on: Jul 23rd, 2007, 2:35am » |
Quote Modify
|
How abt my soln....does it not confirms to what actually the problem states....
ne comments....
i dont understand these bit fiddlings at all....  
|
|
IP Logged |
|
|
|
I_am_searching
Newbie
Gender:
Posts: 30
|
|
Re: A puzzler
« Reply #19 on: Jul 23rd, 2007, 2:37am » |
Quote Modify
|
and now i have started hating these bit manipulation operations as I screwed up My google 3rd interview today jus beacuse of these bits...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #20 on: Jul 23rd, 2007, 2:39am » |
Quote Modify
|
on Jul 23rd, 2007, 2:35am, I_am_searching wrote:How abt my soln....does it not confirms to what actually the problem states....
ne comments....
i dont understand these bit fiddlings at all.... |
|
Yeah, yours works too (although there's still a small mistake where you subtract "0" instead of '0'; subtracting c-strings from characters will give weird results if it works). The main difference is you solve it in decimal rather than binary; and with the conversion to string it will be a bit slower.
|
| « Last Edit: Jul 23rd, 2007, 2:39am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
I_am_searching
Newbie
Gender:
Posts: 30
|
|
Re: A puzzler
« Reply #21 on: Jul 23rd, 2007, 2:41am » |
Quote Modify
|
yeah towr....
I approached the problem as it was stated ...... I need to start thinking out of the box!!!!!! 
|
|
IP Logged |
|
|
|
Shashikant
Newbie
 
Gender:
Posts: 2
|
|
Re: A puzzler
« Reply #22 on: Jul 25th, 2007, 12:29am » |
Quote Modify
|
int ans=0;
While(num<=3)
{
num = num-3;
ans = ans+1;
}
if(num==0)
printf("Number is divisible by 3 and Answer is %d",ans);
else
printf("Number not divisible by 3 and Answer is %d and remainder is %d",ans,num);
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #23 on: Jul 25th, 2007, 12:42am » |
Quote Modify
|
on Jul 25th, 2007, 12:29am, Shashikant wrote:int ans=0;
While(num<=3)
{
num = num-3;
ans = ans+1;
}
if(num==0)
printf("Number is divisible by 3 and Answer is %d",ans);
else
printf("Number not divisible by 3 and Answer is %d and remainder is %d",ans,num); |
|
That while condition seems a bit suspect, and it would take very long for large numbers.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
GowriKumar
Junior Member
Gender:
Posts: 55
|
|
Re: A puzzler
« Reply #24 on: Jul 25th, 2007, 10:19pm » |
Quote Modify
|
on Jul 22nd, 2007, 1:53am, u_think_u_succeed wrote:Given a number, how can u determine using C, whether it is divisible by 3, without using *, /, % operators.
You may assume that itoa() function is available. |
|
Here is what I can think of :
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 dicisible by 3, then the original number is divisible by 3. The implementation of it is as follows (the code also includes the verification part):
Code:
#include <stdio.h>
#include <assert.h>
int arr[32] = {1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0};
int main()
{
int sign ;
int sum ;
int num ;
int i;
for(i=0;i<1000000;i++)
{
sign = 1;
sum = 0;
num = i;
while(num)
{
if(num&1)
{
sum += sign;
}
sign = -sign;
num = num >> 1;
}
if(sum<0)
sum = -sum;
printf("i : %d\n",i);
assert ( (arr[sum]) == (i%3==0));
}
return 0;
}
|
|
There is further optimization possible:
It is possible to do away with the array. We can try simulating a finite state machine which keeps track of the modulo 3, with the sum.
|
|
IP Logged |
www.gowrikumar.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print