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(dynamic programming)

Question

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;
  }
}

Answer 1

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.)

Answer 2

I'm not too convinced about the dynamic programming approach. If I understand correctly, you would need to define how to go to dp[g + 1][h][k][n], dp[g][h + 1][k][n], dp[g][h][k + 1][n] and dp[g][h][k][n + 1], with and without the carry bit, in function of previous computations, and I'm not sure about what are the right rules for all of those.

I think an easier way to think of the problem is as an A* search tree, where each node contains two partial candidate numbers to add, let's call them G and H. You start with a node with G = 0 and H = 0 at level m = 0, and work as follows:

1. If G + H has n or fewer bits and k 1 bits, that's the solution, you found it!
2. Otherwise, if
   n - m < number of 1 bits in G + H - k
   discard the node (no solution possible).
3. Otherwise, if
   (g + h) - (number of 1 bits in G + number of 1 bits in H) < k - number of 1 bits in G + H
   discard the node (not viable candidates).
4. Otherwise, branch the node into a new level. Generally you make up to four children of each node, prefixing G and H with 0 and 0, 0 and 1, 1 and 0 or 1 and 1 respectively. However:
   • You can only precede G with a 1 if the number of 1 bits in G is fewer than g, and similarly for H and h.
   • At level m (G and H have m bits), you can only precede G with a 0 if
     n - m > g - number of 1 bits in G
     and similarly for H and h.
   • If G == H and g == h, you can skip one of 0 and 1 and 1 and 0, since they will lead to the same subtree.
5. Continue to the next node and repeat until you find a solution or you don't have any more nodes to visit.

The order in which you visit the nodes is important. You should store the nodes in a priority queue/heap such that the next node is always the first node that could potentially lead to the best solution. This is actually easy, you just need to take for each node G + H and prefix it with the necessary number of 1 bits to reach k; that's the best possible solution from there.

There are possibly better rules to discard invalid nodes (steps 2 and 3), but the idea of the algorithm is the same.