Efficient method to check if a number is multiple of 3
In binary representation of a number, if difference between even set bit and odd set bit is a multiple of 3.
For example:
12 = 0000 1100
difference = 0
since 0 is a multiple of any integer, 12 is multiple of 3..
Code:
import java.util.*;
public class Solution {
static int ismultipleof3(int num){
int evencount = 0;
int oddcount = 0;
if(num < 0)
num = -num;
if(num == 0) return 0;
if(num == 1) return 1;
while(num != 0){
if((num & 1) != 0){
oddcount++;
}
num = num>>1;
if((num & 1) != 0){
evencount++;
}
num = num>>1;
}
//System.out.println(Math.abs(oddcount-evencount));
return ismultipleof3(Math.abs(oddcount-evencount));
}
public static void main(String[] args) {
int num = 6;
int result = ismultipleof3(num);
if(result==0){
System.out.print(num+" is a multiple of 3");
}
else{
System.out.print(num+" is not a multiple of 3");
}
}
}
Output:
6 is a multiple of 3
Comments
Post a Comment