CODEWITHSUNDEEP
c#arraysalgorithmmathlinear-algebra
mister_giga
mister_giga

Reputation: 612

Algorithm to get which values make sum of a given number from array

I don't know to search or google it so I ask it here. I have an array of integers with fixed size and exactly with this logic.

sample [1,2,4,8,16,32]

Now I am given a number for example 26. And I shall find the numbers whose sum will make this number, in this case is [2,8,16]

for a number of 20 it will be [4,16]

for 40 it is [8,32]

and for 63 it is all of these numbers [1,2,4,8,16,32]

What is the proper algorithm for that?

I know strictly that there is always this continuation that the number is double of the previous value. as well as only the numbers from the given array will sum up to the given number and each number will be used only for once or none

If it will be in C# method that takes array of ints and an int value and returns the array of ints that contains the ints that sum up this number from the given array will be preferred.

Thank you

Upvotes: 6

Views: 1647

Answers (4)

Richard II
Richard II

Reputation: 871

Another way to state your requirement is "What are the unique powers of 2 that sum to a given integer?" Since computers work with powers of 2 natively, there are built-in goodies in most languages to do this very succinctly.

As a bonus, you can use existing .Net types and methods to eliminate the need to write your own loops.

Here's one approach:

IEnumerable<int> GetCompositePowersOf2(int input) =>
    //convert to enumerable of bools, one for each bit in the 
    //input value (true=1, false=0)
    new BitArray(new[] { input }).Cast<bool>()
    // get power of 2 corresponding to the position in the enumerable 
    // for each true value, gets 0 for false values.
    .Select((isOne, pos) => isOne ? (1 << pos) : 0)
    //filter out the 0 values
    .Where(pow => pow > 0);

Upvotes: 1

Jeroen van Langen
Jeroen van Langen

Reputation: 22038

As you can see, the number are base-2, which means you can easily use shift.

You could try this:

private IEnumerable<int> FindBits(int value)
{
    // check for bits.
    for (int i = 0; i < 32; i++)
    {
        // shift 1 by i
        var bitVal = 1 << i;   // you could use (int)Math.Pow(2, i); instead
        // check if the value contains that bit.
        if ((value & bitVal) == bitVal)
            // yep, it did.
            yield return bitVal;
    }
}

This method will check what bits are set and return them as an ienumerable. (which can be converted to an array of list)

Usage:

// find the bits.
var res = FindBits(40).ToArray();

// format it using the string.join
var str = $"[{string.Join(",", res)}]";

// present the results
Console.WriteLine(str);

Results in [8,32]

Extra info:

                          counter
00000001 =   1     = 1 << 0
00000010 =   2     = 1 << 1 
00000100 =   4     = 1 << 2
00001000 =   8     = 1 << 3
00010000 =  16     = 1 << 4
00100000 =  32     = 1 << 5
01000000 =  64     = 1 << 6
10000000 = 128     = 1 << 7

Instead of writing all combinations you make a for loop which does the counter.

Some extra non-sense:

If you like lambda's, you could replace the FindBits with this:

private Func<int, IEnumerable<int>> FindBits = (int value) => Enumerable
    .Range(0, 31)
    .Select(i => 2 << i).Where(i => (value & i) == i);

But it's better to keep it simpel/readable.

Upvotes: 4

Judit
Judit

Reputation: 134

I don't quite get the " takes array of ints " part, since this creation of sums only works with numbers that are the power of 2. 

    private int[] count (int num)
    {

        int factor = 0;
        List<int> facts = new List<int>();
        while (num > 0)
        {
            int counter = 0;
            int div = num;
            int remainder = 0;
            while (remainder == 0)
            {
                remainder = div % 2;
                div = div / 2;
                counter++;
            }
            factor = 1;
            for (int i = 1; i < counter; i++) 
                factor *= 2;
            num = num - factor;
            facts.Add(factor);
        }

        return (facts.ToArray());
    }

Upvotes: 0

gbtimmon
gbtimmon

Reputation: 4322

First you should notice that 

 ( 1    2    4    8    16 ... ) = (2^0  2^1  2^2  2^3  2^4 ... )

And that this is the same as finding a binary encoding for a decimal number. What you are looking for is an algorithm to transform a decimal or base 10 number to a binary or base 2 number.

The algorithm is pretty simple: 

public List<int> dec_to_bin(int num)
{
    List<int> return_list = new List<int>();
    int index = 0; 
    int remainder = num;
    int bit = 0;

    while (remainder > 0)
    {
        bit = remainder % 2;

        if (bit == 1 )
        {
            return_list.Add((int)Math.Pow(2, index));
        }

        remainder = remainder / 2; 
        index = index + 1;
   }

   return return_list;
}

There is a better way however that just uses the underlying encoding of the number which is already binary. 

public List<int> dec_to_bin(int num)
{
    List<int> return_list = new List<int>();
    int value = 1; 

    while( value < num )
    {
         if( (value & num) == value )
         {
             return_list.Add(value);
         }
         value = value * 2; 
    }
    return return_list;
}

Upvotes: 2

Related Questions