Advertisement
saurav_kalsoor

Special Sum - JAVA

Aug 14th, 2022
708
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Author : Saurav Kalsoor
  2. // Special Sum - JAVA
  3.  
  4.  
  5. import java.util.*;
  6.  
  7. public class Test {
  8.    
  9.     static Scanner sc = new Scanner(System.in);
  10.  
  11.     public static void main(String[] args) {
  12.         int n = sc.nextInt();
  13.         System.out.println(specialSum(n));
  14.     }
  15.  
  16.     public static int specialSum(int n){
  17.         ArrayList<Integer> fact = new ArrayList<>();
  18.         TreeMap<Integer, Integer> sums = new TreeMap<>();
  19.  
  20.         int i = 2, x = 1;
  21.         int maxLimit = 100000000;
  22.         while(x < maxLimit){
  23.             fact.add(x);
  24.             x *= i;
  25.             i++;
  26.         }
  27.  
  28.         int limit = (int)Math.pow(2, 11);
  29.    
  30.         for(i = 1; i < limit; i++){
  31.             int sum = 0;
  32.             for(int j = 0; j < 11; j++){
  33.                 if((i & (1 << j)) > 0){
  34.                     sum += fact.get(j);
  35.                 }
  36.             }
  37.             sums.put(sum, Math.min(bitCount(i), sums.containsKey(sum) ? sums.get(sum) : limit));
  38.         }
  39.  
  40.         int res = bitCount(n);
  41.         for(Map.Entry<Integer, Integer> sum : sums.entrySet()){
  42.             if(sum.getKey() > n) break;
  43.  
  44.             res = Math.min(res, bitCount(n - sum.getKey()) + sum.getValue());
  45.         }
  46.         return res;
  47.     }
  48.    
  49.     public static int bitCount(int n){
  50.         int res = 0;
  51.         while(n > 0){
  52.             res += n%2;
  53.             n /= 2;
  54.         }
  55.         return res;
  56.     }
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement