View difference between Paste ID: UpBZMgSk and QEeYYCrA

 // Author : Saurav Kalsoor
-// Duplicate Bogies - JAVA
+// 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));
-		ArrayList<Integer> arr = new ArrayList<>();
+
-		for(int i=0; i < n ;i++){
+
-			arr.add(sc.nextInt());
+	public static int specialSum(int n){
 		ArrayList<Integer> fact = new ArrayList<>();
-		System.out.println(duplicateBogies(n, arr));
+		TreeMap<Integer, Integer> sums = new TreeMap<>();
 
 		int i = 2, x = 1;
-	public static int duplicateBogies(int n, ArrayList<Integer> arr){
+		int maxLimit = 100000000;
-		HashSet<Integer> st = new HashSet<>();
+		while(x < maxLimit){
-		int res = n;
+			fact.add(x);
-		for(int x : arr){
+			x *= i;
-			if(st.contains(x)){
+			i++;
-				res = (n - st.size());
+
-				break;
+
 		int limit = (int)Math.pow(2, 11);
-			st.add(x);
+
 		for(i = 1; i < limit; i++){
 			int sum = 0;
-		Collections.reverse(arr);
+			for(int j = 0; j < 11; j++){
-		st.clear();
+				if((i & (1 << j)) > 0){
-
+					sum += fact.get(j);
-		for(int x : arr){
+				}
-			if(st.contains(x)){
+
-				res = Math.min(res, (n - st.size()));
+			sums.put(sum, Math.min(bitCount(i), sums.containsKey(sum) ? sums.get(sum) : limit));
-				break;
+
 
-			st.add(x);
+		int res = bitCount(n);
 		for(Map.Entry<Integer, Integer> sum : sums.entrySet()){
 			if(sum.getKey() > n) break;
-		if(res == n) res = 0;
+
 			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;
 	}
 }