I am trying to solve the following problem:
Find the smallest n-bit integer c that has k 1-bits and is the sum of two n-bit integers that have g, h bits set to 1. g, h, k <= n
To start with, n-bit integer here means that we may use all n bits, i.e. max. value of such an integer is 2^n - 1. The described integer may not exist at all.
It is obvious the case k > g + h has no solutions and for g + h = k the answer is just 2^k - 1 (first k bits are 1-bits, k - n zeroes in the front).
As for some examples of what the program is supposed to do:
g = h = k = 4, n = 10 :
0000001111 + 0000001111 = 0000011110
15 + 15 = 30 (30 should be the output)
(4, 6, 5, 10):
0000011110 + 0000111111 = 0001011101
30 + 63 = 93
(30, 1, 1, 31):
1 + (2^30 - 1) = 2^30
As I think of it, this is a dynamic programming problem and I've chosen the following approach:
Let dp[g][h][k][n][c] be the described integer and c is an optional bit for carrying. I try to reconstruct possible sums depending on the lowest-order bits.
So, dp[g][h][k][n + 1][0] is the minimum of
(0, 0): dp[g][h][k][n][0]
(0, 0): 2^n + dp[g][h][k - 1][n][1]
(1, 0): 2^n + dp[g - 1][h][k - 1][n][0]
(0, 1): 2^n + dp[g][h - 1][k - 1][n][0]
Similarly, dp[g][h][k][n + 1][1] is the minimum of
(1, 1): dp[g - 1][h - 1][k][n][0]
(1, 1): dp[g - 1][h - 1][k - 1][n][1] + 2^n
(1, 0): dp[g - 1][h][k][n][1]
(0, 1): dp[g][h - 1][k][n][1]
The idea isn't that hard but I'm not really experienced with such things and my algorithm doesn't work even for simplest cases. I've chosen top-down approach. It's hard for me to consider all the corner cases. I do not really know if I've properly chosen base of recursion, etc. My algorithm doesn't even work for the most basic case for g = h = k = 1, n = 2(the answer is 01 + 01 = 10). There shouldn't be an answer for g = h = k = 1, n = 1 but the algorithm gives 1(which is basically why the former example outputs 1 instead of 2).
So, here goes my awful code(only very basic C++):
int solve(int g, int h, int k, int n, int c = 0) {
if (n <= 0) {
return 0;
}
if (dp[g][h][k][n][c]) {
return dp[g][h][k][n][c];
}
if (!c) {
if (g + h == k) {
return dp[g][h][k][n][c] = (1 << k) - 1;
}
int min, a1, a2, a3, a4;
min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
if (g + h > k && k <= n - 1) {
a1 = solve(g, h, k, n - 1, 0);
}
if (g + h >= k - 1 && k - 1 <= n - 1) {
a2 = (1 << (n - 1)) + solve(g, h, k - 1, n - 1, 1);
}
if (g - 1 + h >= k - 1 && k - 1 <= n - 1) {
a3 = (1 << (n - 1)) + solve(g - 1, h, k - 1, n - 1, 0);
}
if (g + h - 1 >= k - 1 && k - 1 <= n - 1) {
a4 = (1 << (n - 1)) + solve(g, h - 1, k - 1, n - 1, 0);
}
min = std::min({a1, a2, a3, a4});
return dp[g][h][k][n][c] = min;
} else {
int min, a1, a2, a3, a4;
min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
if (g - 2 + h >= k && k <= n - 1) {
a1 = solve(g - 1, h - 1, k, n - 1, 0);
}
if (g - 2 + h >= k - 1 && k - 1 <= n - 1) {
a2 = (1 << (n - 1)) + solve(g - 1, h - 1, k - 1, n - 1, 1);
}
if (g - 1 + h >= k && k <= n - 1) {
a3 = solve(g - 1, h, k, n - 1, 1);
}
if (g - 1 + h >= k && k <= n - 1) {
a4 = solve(g, h - 1, k, n - 1, 1);
}
min = std::min({a1, a2, a3, a4});
return dp[g][h][k][n][c] = min;
}
}
You can construct the smallest sum based on the bit counts g, h, and k, without doing any dynamic programming at all. Assuming that g ≥ h (switch them otherwise) these are the rules:
k ≤ h ≤ g
11111111 <- g ones
111100000111 <- h-k ones + g-k zeros + k ones
1000000000110 <- n must be at least h+g-k+1
h ≤ k ≤ g
1111111111 <- g ones
11111100 <- h ones + k-h zeros
1011111011 <- n must be at least g+1
h ≤ g ≤ k
1111111100000 <- g ones + k-g ones
1100000011111 <- g+h-k ones, k-h zeros, k-g ones
11011111111111 <- n must be at least k+1, or k if g+h=k
Example: all values of k for n=10, g=6 and h=4:
k=1 k=2 k=3 k=4
0000111111 0000111111 0000111111 0000111111
0111000001 0011000011 0001000111 0000001111
---------- ---------- ---------- ----------
1000000000 0100000010 0010000110 0001001110
k=4 k=5 k=6
0000111111 0000111111 0000111111
0000001111 0000011110 0000111100
---------- ---------- ----------
0001001110 0001011101 0001111011
k=6 k=7 k=8 k=9 k=10
0000111111 0001111110 0011111100 0111111000 1111110000
0000111100 0001110001 0011000011 0100000111 0000001111
---------- ---------- ---------- ---------- ----------
0001111011 0011101111 0110111111 1011111111 1111111111
Or, going straight to the value of c without calculating a and b first:
k ≤ h ≤ g
c = (1 << (g + h - k)) + ((1 << k) - 2)
h ≤ k ≤ g
c = (1 << g) + ((1 << k) - 1) - (1 << (k - h))
h ≤ g ≤ k
c = ((1 << (k + 1)) - 1) - (1 << ((g - h) + 2 * (k - g)))
h + g = k
c = (1 << k) - 1
which results in this disappointingly mundane code:
int smallest_sum(unsigned n, unsigned g, unsigned h, unsigned k) {
if (g < h) {unsigned swap = g; g = h; h = swap;}
if (k == 0) return (g > 0 || h > 0 || n < 1) ? -1 : 0;
if (h == 0) return (g != k || n < k) ? -1 : (1 << k) - 1;
if (k <= h) return (n <= h + g - k) ? -1 : (1 << (g + h - k)) + ((1 << k) - 2);
if (k <= g) return (n <= g) ? -1 : (1 << g) + ((1 << k) - 1) - (1 << (k - h));
if (k < g + h) return (n <= k) ? -1 : (1 << (k + 1)) - 1 - (1 << (2 * k - g - h));
if (k == g + h) return (n < k) ? -1 : (1 << k) - 1;
return -1;
}
Some example results:
n=31, g=15, h=25, k=10 -> 1,073,742,846 (1000000000000000000001111111110)
n=31, g=15, h=25, k=20 -> 34,602,975 (0000010000011111111111111011111)
n=31, g=15, h=25, k=30 -> 2,146,435,071 (1111111111011111111111111111111)
(I compared the results with those of a brute-force algorithm for every value of n, g, h and k from 0 to 20 to check correctness, and found no differences.)