Special Sum - JAVA

// Author : Saurav Kalsoor
// Special Sum - JAVA


import java.util.*;

public class Test {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        System.out.println(specialSum(n));
    }

    public static int specialSum(int n){
        ArrayList<Integer> fact = new ArrayList<>();
        TreeMap<Integer, Integer> sums = new TreeMap<>();

        int i = 2, x = 1;
        int maxLimit = 100000000;
        while(x < maxLimit){
            fact.add(x);
            x *= i;
            i++;
        }

        int limit = (int)Math.pow(2, 11);

        for(i = 1; i < limit; i++){
            int sum = 0;
            for(int j = 0; j < 11; j++){
                if((i & (1 << j)) > 0){
                    sum += fact.get(j);
                }
            }
            sums.put(sum, Math.min(bitCount(i), sums.containsKey(sum) ? sums.get(sum) : limit));
        }

        int res = bitCount(n);
        for(Map.Entry<Integer, Integer> sum : sums.entrySet()){
            if(sum.getKey() > n) break;

            res = Math.min(res, bitCount(n - sum.getKey()) + sum.getValue());
        }
        return res;
    }

    public static int bitCount(int n){
        int res = 0;
        while(n > 0){
            res += n%2;
            n /= 2;
        }
        return res;
    }
}