All possible numbers formed from addition of given digits

Question

If I have n-r numbers, from 1 to n where r numbers are missing in between, then how can I calculate all possible numbers that can be formed from addition of these numbers (either in groups of 2/3/4/5/6...).

For example, lets say I have 5-2 numbers, that is, 1 2 4 and 3 5 are missing. Now, I can form

1 - {1}
2 - {2}
3 - {1,2}
4 - {4}
5 - {1,4}
6 - {4,2}
7 - {1,2,4}
8 - Cannot be formed

This is I need to find out, that is the first number from 1 which I cannot form using the combination of the given digits. A simple logic would do fine. Thanks!

Answer 1

Let S[i] be the set of numbers that can be formed from the first i of your numbers. Then given S[i], it is easy to construct S[i+1]: start with S[i], and then add all numbers of the form s+r, where s is in S[i] and r is the (i+1)-th number in your list.

Thus you can iteratively build the sets s[0] = {0}, S[1],...,S[n-r], and S[n-r] contains all possible sums.

Here is how your example plays out:

S[0] = {0}
r = 1: S[1] = {0} union {0+1} = {0,1}
r = 2: S[2] = {0,1} union {0+2,1+2} = {0,1,2,3}
r = 4: S[3] = {0,1,2,3} union {0+4,1+4,2+4,3+4} = {0,1,2,3,4,5,6,7}

Answer 2

1. Start with a set containing 0
2. Find all possible sums of the set and your first number (so if your first number is 1 then your set contains 1 and 0)
3. Now add in the next number (so if your next number is 2 your set contains 0, 1, 2, and 3)
4. So on...

That set contains all possible numbers. You'll need to itterate through the set and find the first gap. This will work even if there are negative numbers in your set.

I know you said you just wanted the logic, but if you want to see a solution mouse over below:

set<int> foo{ 0 };
vector<int> numbers{ 4, 1, 2 };

for (auto& i : numbers){
set<int> temp;

for_each(foo.begin(), foo.end(),[&](int j){temp.insert(i + j);});
foo.insert(temp.begin(), temp.end());
}

for (auto& i : foo){
cout << i << endl;
}
cout << "First number that cannot be formed " << *mismatch(foo.begin(), prev(foo.end()), next(foo.begin()), [](int first, int second){return first + 1 == second;}).first + 1 << endl;

If you're trying to implement the search for a gap in your set using an STL algorithm, I found that somewhat difficult. The problem is that you need to separate your iterator's incrementation from its comparison.

So for example this won't work:

auto i = foo.begin();
while (++i != prev(foo.end()) && *prev(i) + 1 == *i);
cout << "First number that cannot be formed " << *prev(i) + 1 << endl;

Because if all numbers are sequential *prev(i) + 1 is the last value in the set.

This option will work:

i = foo.begin();
while (i != prev(foo.end()) && *i + 1 == *next(i)){
    ++i;
}
cout << "First number that cannot be formed " << *i + 1 << endl;

But this assumes that your set always contains at least 0.

Answer 3

The logic is to build all the possible sums for each successive integer, starting from 1. The problem can be simplified by keeping track of all the possible sums and checking only for sums of pairs of integer. The pseudocode (untested and buggy) would look like:

const std::vector<unsigned> l = {1,2,4};
const unsigned sum = std::accumulate(l.begin(), l.end());
typedef std::vector<unsigned> Sum; // one possibility for a single value
typedef std::vector<Sum> Sums; // all possibilities for a single value
// the element all[i] will provide all possible subsets where the sum is equal to 'i'
std::vector<Sums> all(sum + 2); // we know that sum + 1 is impossible
// initialize with single values
for (auto i: l)
{
    all[i].push_back(Vector(1, i));
}
unsigned i = 1; // ignore 0
// stop as soon as a value doesn't have any subset
while (!all[i].empty())
{
    ++i;
    for (unsigned j = 1; i/2 > j; ++j)
    {
        const unsigned k = i - j;
        // as i == j+k, create all the relevant combinations
        for (const auto &sj: all[j])
        {
            for (const auto &sk: all[k])
            {
                all[i].push_back(sj);
                all[i].back.insert(all[i].end(), sk.begin(), sk.end());
            }
        }
    }
    if (0 == (i % 2))
    {
        // create all the possible decompositions out of i/2
        for (auto left = all[i/2].begin(); all[i/2].end() != left; ++left)
        {
            for (auto right = left + 1; all[i/2].end() != right; ++ right)
            {
                all[i].push_back(*left);
                all[i].back.insert(all[i].end(), right->begin(), right->end());
            }
        }
    }
}

One of the bugs that need to be addressed: rejecting sums where the same number appears more than once.

Answer 4

For input sets or multisets which only contain positive integers, Evgeny Kluev's Solution is O(2n), [my other solution] is O(nlogn).

For a given input numbers you can find the unformable number as follows:

1. Collect elements of number into int_log[i] where i = int(log2(element))
2. Find S[] which is the prefix sum of int_log[]
3. The first unformable number is S[x] + 1 where int_log[x + 1] contains no element less than or equal to S[x] + 1

For a proof that all numbers in the range [0, S[i]] can be formed by subset of int_log smaller than 2^i-1 see: https://math.stackexchange.com/questions/1099359/0-sum-representable-by-numbers-in-a-set

set<int> numbers{ 1, 2, 5, 6, 7 };
unordered_multimap<unsigned long, decltype(numbers)::key_type> int_log;

for (auto& value : numbers){
    auto key = decltype(int_log)::key_type{};

    _BitScanReverse(&key, value); //If using gcc you'll need to use __builtin_clz here
    int_log.insert(make_pair(key, value));
}

auto result = decltype(numbers)::key_type{}; // Because we only ever need to look at the previous prefix sum value we'll use previousSum instead of a S[] here
auto sum = decltype(numbers)::key_type{};
auto i = decltype(int_log)::key_type{};
auto smallest = decltype(numbers)::key_type{};

do{
    result = sum;
    smallest = 2 << i;

    for (auto range = int_log.equal_range(i); range.first != range.second; ++range.first){
        const auto current = range.first->second;

        sum += current;
        smallest = min(smallest, current);
    }
    ++i;
} while (result >= smallest - 1);
cout << "First number that cannot be formed: " << result + 1 << endl;