Unique Combination of Factors, Factorial Trailing Zeroes

Unique Combination of Factors

Print all unique combinations of factors of a positive integer. For example given 24:

24*1
12*2
8*3
6*4
6*2*2
4*3*2
3*2*2*2

Solution

Reverse DFS all possible division combinations. Keep track of current dividend, try all divisors. Use backtracking to gather all all possible division combinations.

     24
  /   |  \
 1    6    24
/ \ / | \  / \
....  2  4 ....
	   |
	  / \
    1   2

public ArrayList<ArrayList<Integer>> factorCombinations(int n){
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		ArrayList<Integer> first=new ArrayList<Integer>();
		first.add(n);first.add(1);
		res.add(first);
		res=dfs(res, n, n/2, tmp);
		return res;
	}

	private ArrayList<ArrayList<Integer>> dfs(ArrayList<ArrayList<Integer>> res, int Curdividend, int Largestdivisor, ArrayList<Integer> tmp){
		if(Curdividend==1){
			res.add(new ArrayList<Integer>(tmp));
			return null;
		}

		for(int i=Largestdivisor; i>1;i--){
			if(Curdividend%i==0){
				tmp.add(i);
				dfs(res,Curdividend/i, i,tmp);
				tmp.remove(tmp.size()-1);
			}
		}
		return res;
	}

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

public int trailingZeroes(int n) {
       if(n<5) return 0;
       int count_of_five=0;
       while(n>1){
           n=n/5;
           count_of_five+=n;
       }
       return count_of_five;
   }