Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // 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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement