- N個の要素の整数を持つ配列Aを与えられる(N >= 1)
- binarian(A) = pow2(A[0]) + pow2(A[1]) + ... + pow2(A[M-1])
- 上記の式で求めた結果と同じ値となるための 2の累乗n の加算 の最小の組み合わせ数を求める
例:
A[0]=1 A[1]=5 A[2]=4 A[3]=4 binarian(A) = pow2(A[0]) + pow2(A[1]) + pow2(A[2]) + pow2(A[3]) = pow2(1) + pow2(5) + pow2(4) + pow2(4) = 2 + 32 + 16 + 16 = 66
この 66 を表現する2の累乗の和の表現は以下になります(2の1乗 + 2の6乗 で表現できます)
66 = pow2(1) + pow2(6)
結果として答えは 2です。(2の1乗 と 2の6乗 の2つの組み合わせで表現できるので)
これを求めるプログラムは以下になります
import java.util.Map; import java.util.TreeMap; public class Solution { public static int solution(int[] A) { TreeMap<Integer, Integer> reiterations = new TreeMap<>(); int lengthSolution = 0; for (int i = 0; i < A.length; i++) { int item = A[i]; if (reiterations.containsKey(item)) { reiterations.put(item, reiterations.get(item) + 1); } else { reiterations.put(item, 1); } } reiterations = factorize(reiterations, reiterations.firstEntry()); for (Map.Entry<Integer,Integer> entry : reiterations.entrySet()) { int value = entry.getValue(); if (value == 1) { lengthSolution++; } } return lengthSolution; } public static TreeMap<Integer, Integer> factorize(TreeMap<Integer, Integer> remaining, Map.Entry<Integer, Integer> entry) { int key = entry.getKey(); int value = entry.getValue(); if (value > 1 && value % 2 == 0) { if (remaining.containsKey(key + 1)) { remaining.put(key + 1, remaining.get(key + 1) + value / 2); remaining.put(key, 0); } else { remaining.put(key + 1, value / 2); remaining.put(key, 0); } } else if (value > 1 && value % 2 == 1) { if (remaining.containsKey(key + 1)) { remaining.put(key + 1, remaining.get(key + 1) + (value - 1) / 2); remaining.put(key, 1); } else { remaining.put(key + 1, (value - 1) / 2); remaining.put(key, 1); } } while (remaining.higherEntry(key) != null) { if (remaining.higherEntry(key).getValue() > 1) { factorize(remaining, remaining.higherEntry(key)); } key++; } return remaining; } }
念のために [1, 5, 4, 4]の配列を渡して試してみると
public class Main { public static void main(String[] args) { int[] test = {1, 5, 4, 4}; System.out.println(Solution.solution(test)); } }
出力結果
2
予定通りの結果が得られています