覚えたら書く

IT関係のデベロッパとして日々覚えたことを書き残したいです。twitter: @yyoshikaw

2の累乗の加算で表現できる値の分解

  • 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

予定通りの結果が得られています