How to check whether a number is divisible by 3 or not without using +,*,-,/,% operators?
If you can use bit operators ( >>, & ), than you can use the property of mod operation
A*B mod 3 = ( (A mod 3) * (B mod 3) ) mod 3
than
1010 = 10102
10 = 23 + 21 = 21 * (22 + 1) = 2 * (2 * 2 + 1)
10 % 3 = ( 2 % 3 * ( ( 2 % 3 * 2 % 3 ) % 3 + 1 % 3 ) % 3 ) % 3
The only problem here is +1 operation, but you can use state machine to compute mod3
last bit | |||
0 | 1 | ||
actual mod | 0 | 0 (2*act. mod+0) | 1 (2*act. mod+1) |
1 | 2 (2*act. mod+0) | 0 (2*act. mod+1) | |
2 | 1 (2*act. mod+0) | 2 (2*act. mod+1) |
I’m not sure if that was clear so I’m adding code in Java:
private static boolean mod3( int n ) {
int mod = 0;
while ( n > 0 ) {
final int bit = n & 1;
if ( bit == 0 ) {
switch ( mod ) {
case 0:
mod = 0; // 2*0;
break;
case 1:
mod = 2; // 2*1;
break;
case 2:
mod = 1; // (2*2) % 3;
break;
}
} else {
switch ( mod ) {
case 0:
mod = 1; // 2*0 + 1
break;
case 1:
mod = 0; // (2*1 + 1) % 3
break;
case 2:
mod = 2; // (2*2 + 1) % 3
break;
}
}
n >>= 1;
}
return mod == 0;
}
1 Like