is3multiple, all permutations of a string, Numbers without a digit, day of the week, Binomial Coefficient, Shuffle array, Reservoir Sampling, BitCount, Moore Voting Algorithm

MathMethods.java

public class MathMethods{
  
  /*********************************************
  IS3MULTIPLE - 
  Checks whether a number is 3 multiple or not 
  much faster - does bitwise operations as follows:
  
  if number is negative make it positive, if it is 0 return 1
  if it is 1 return 0, count number of odd set bits and even set
  bits and perform this operation recursively
  
  [refer - http://www.geeksforgeeks.org/write-an-efficient-method-to-check-if-a-number-is-multiple-of-3/]
  
  **********************************************/
  
  public static int is3Multiple(int n){		
		n = Math.abs(n);
		if(n==0) return 1;
		if(n==1) return 0;		
		int oddBits=0,evenBits=0;
		while(n>=1){			
			if((n&1) ==1){++oddBits;}
			n = n>>1;			
			if((n&1) ==1){++evenBits;}
			n = n>>1;			
		}		
		return isMultiple(Math.abs(oddBits-evenBits));		
	}
  
  /*************************************************
  PRINT ALL PERMUTATIONS OF A STRING:  
  *************************************************/
  public static void printPerms(String pre, String cur){
		if(cur.length()==0) {System.out.println(pre);return;}		
		for(int i=0; i<cur.length(); i++){
			
			String str = "";
			if(i>0) str+= cur.substring(0, i);
			if(i<cur.length()-1) str+= cur.substring(i+1);
			
			printPerms(pre+cur.charAt(i),str);			
		}		
	}
  /*************************************************
 	Numbers without a digit (q):
	if given N, the last digit, else go for a msd sort
	and count the numbers while doing the process
  *************************************************/
  int q; //Initialize it with any digit
  public static int count(int n){
  	if(n<q) {return n;}
	else if(0<n<10) {return n-1;}  
	
	int po=1;
	while(po<n){
	   po=po*10;
	}
	
	int msd = n/po;
	if(msd!=q){ return count(msd)*count(po-1)+count(msd)+count(n%po);}
	else {  return count(msd*po-1);	}  
  }
  
  /*************************************************
 	Day of the week : 
  *************************************************/
	
  int dayOfWeek(int d, int m, int y){
  	static int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
    return ( y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
  }
	
  /*************************************************
 	Binomial Coefficient : 
	Time: O(k) Space:O(1)
  *************************************************/
  public int binomialCoefficient(int n, int k){
  		
	  int res=1;
	  if(k>n-k) k=n-k;
	  for(int i=0; i<k; i++){	  	
		  res*=(n-i);
		  res/=(i+1);		  
	  }
	  
	  return res; 
  }
	
  /*************************************************
 	Fisher-Yates Shuffle Algorithm:
  *************************************************/
  public void swap(int[] arr,int i, int j){  	
	  int temp=arr[i]; 
	  arr[i]=arr[j];
	  arr[j]=temp;
  }

  public void shuffle(int[] arr){

	  int n=arr.length;
	  for(int i=n-1; i>=0; i--){	  	
		  int rd = (int)Math.random()*(i);
		  swap(arr,rd,i);
	  }
  }
	
  /*************************************************
 	Reservoir Sampling: Select k random numbers from
	an input stream of an unknown size (n>k)
	Great proof - [refer- http://www.geeksforgeeks.org/reservoir-sampling/]
  *************************************************/
	public int[] reservoirSampling(int[] stream,int k){
		int[] reser = new int[k];
		for(int i=0; i<k; i++){
			reser[i]=stream[i];
		}
		for(int i=k;i<stream.length; i++){
			int rd = (int)Math.random()*i;
			if(rd<k){
				reser[rd]=stream[i];
			}
		}
		return reser;
	}
	
  /*************************************************
 	BitCount: Brian Kernighan's 
  *************************************************/
	public static int btCount(long n){
		int count=0;
		while(n>0){
			n&=(n-1);
			++count;
		}
		return count;
	}
	
/*************************************************
 	Moore's Voting Algorithm: To find the element
	occuring more than n/2 times - O(n)
	A check has to be performed whether its right!
  *************************************************/	
	public static int isMajority(int[] ar){
		int N = ar.length;
		int count=0, maj_ind=0;
		for(int i=1; i<N; i++){
			if(ar[i]==ar[maj_ind]){
				++count;
			} else {
				--count;
			}
			
			if(count==0){
				maj_ind=i; count=1;
			}
		}
		
		return ar[maj_ind];	
	}
	
/*************************************************
 	BitCount: Brian Kernighan's 
  *************************************************/
  
  
  
  

}