これは、入力状態 (xor 桁、和桁、入力キャリー) に対して出力状態 (出力キャリー) の数が限られていることを認識することで解決できます。条件を使用して各状態に対処し、if再帰を使用して組み合わせの総数を計算できます。メモ化を使用して、再帰を効率的にすることができます。以下の私の解決策は、数値データ型の2進数字の数である問題をO(m)時間内に解決します。問題は(整数) をm指定しているため、これは技術的には解決策です。m = 32O(1)
ご不明な点がございましたら、お知らせください。さまざまなケースを説明するために、コードに役立つコメントを追加しようとしました。
public class SumAndXor {
public static void main(String[] args) {
int a = 3;
int b = 7;
int sum = a + b;
int xor = a ^ b;
System.out.println(answer(sum, xor));
}
private static final int NOT_SET = -1;
// Driver
public static int answer(int sum, int xor) {
int numBitsPerInt = Integer.toBinaryString(Integer.MAX_VALUE).length() + 1;
int[][] cache = new int[numBitsPerInt][2];
for (int i = 0; i < numBitsPerInt; ++i) {
cache[i][0] = NOT_SET;
cache[i][1] = NOT_SET;
}
return answer(sum, xor, 0, 0, cache);
}
// Recursive helper
public static int answer(int sum, int xor, int carry, int index, int[][] cache) {
// Return memoized value if available
if (cache[index][carry] != NOT_SET) {
return cache[index][carry];
}
// Base case: nothing else to process
if ((sum >> index) == 0 && (xor >> index) == 0 && carry == 0) {
return 1;
}
// Get least significant bits
int sumLSB = (sum >> index) & 1;
int xorLSB = (xor >> index) & 1;
// Recursion
int result = 0;
if (carry == 0) {
if (xorLSB == 0 && sumLSB == 0) {
// Since the XOR is 0, the binary digits are either [0, 0] or [1, 1]. Since the
// sum is 0 and the incoming carry is 0, both [0, 0] and [1, 1] are valid. We
// recurse with a carry of 0 to represent [0, 0], and we recurse with a carry of
// 1 to represent [1, 1].
result = answer(sum, xor, 0, index + 1, cache) + answer(sum, xor, 1, index + 1, cache);
} else if (xorLSB == 0 && sumLSB == 1) {
// Since the XOR is 0, the binary digits are either [0, 0] or [1, 1]. Since the
// sum is 1 and the incoming carry is 0, neither [0, 0] nor [1, 1] is valid.
result = 0;
} else if (xorLSB == 1 && sumLSB == 0) {
// Since the XOR is 1, the binary digits are either [0, 1] or [1, 0]. Since the
// sum is 0 and the incoming carry is 0, neither [0, 1] nor [1, 0] is valid.
result = 0;
} else if (xorLSB == 1 && sumLSB == 1) {
// Since the XOR is 1, the binary digits are either [0, 1] or [1, 0]. Since the
// sum is 1 and the incoming carry is 0, both [0, 1] and [1, 0] is valid. We
// recurse with a carry of 0 to represent [0, 1], and we recurse with a carry
// of 0 to represent [1, 0].
result = 2 * answer(sum, xor, 0, index + 1, cache);
}
} else {
if (xorLSB == 0 && sumLSB == 0) {
// Since the XOR is 0, the binary digits are either [0, 0] or [1, 1]. Since the
// sum is 0 and the incoming carry is 1, neither [0, 0] nor [1, 1] is valid.
result = 0;
} else if (xorLSB == 0 && sumLSB == 1) {
// Since the XOR is 0, the binary digits are either [0, 0] or [1, 1]. Since the
// sum is 1 and the incoming carry is 1, both [0, 0] and [1, 1] are valid. We
// recurse with a carry of 0 to represent [0, 0], and we recurse with a carry of
// 1 to represent [1, 1].
result = answer(sum, xor, 0, index + 1, cache) + answer(sum, xor, 1, index + 1, cache);
} else if (xorLSB == 1 && sumLSB == 0) {
// Since the XOR is 1, the binary digits are either [0, 1] or [1, 0]. Since the
// sum is 0 and the incoming carry is 1, both [0, 1] and [1, 0] are valid. We
// recurse with a carry of 0 to represent [0, 1], and we recurse with a carry
// of 0 to represent [1, 0].
result = 2 * answer(sum, xor, 1, index + 1, cache);
} else if (xorLSB == 1 && sumLSB == 1) {
// Since the XOR is 1, the binary digits are either [0, 1] or [1, 0]. Since the
// sum is 1 and the incoming carry is 1, neither [0, 1] nor [1, 0] is valid.
result = 0;
}
}
cache[index][carry] = result;
return result;
}
}