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

Popular posts from this blog

Rearrange Array in Maximum-Minimum form

Find Maximum in Binary Tree