CODEWITHSUNDEEP
algorithmsequence
Hanne Smith
Hanne Smith

Reputation: 207

Calculate numbers used from a sequence

I got the following sequence of numbers 1,2,4,8,16,32,64....8192 - where each of the numbers represent something, like 1 could represent "Milk", and 2 could represent "Egg".

I got a cupcake with the value of 3. Since 1 + 2 = 3, I know that my cupcake contains both milk(1) and eggs(2).

However - I'm looking for an algorithm to help me achieve this. If the sum is 1536 I would like the algorithm to find 1024 and 512 - or, if the sum is 7 - numbers used would be: 1,2,4.

Is there a way to do this?

Upvotes: 3

Views: 233

Answers (3)

Jhuliano Moreno
Jhuliano Moreno

Reputation: 989

Let's see if I understood, you have a sequence that is basically "binary" (power of 2) values, ex:

32---16---8----4----2-----1

0----0----0----1----1-----0 is 6

So you can go ahead and convert your input number (which is an int) to binary and then go bit by bit checking if they are turned on.

So lets say you have the number 35, to binary:

32---16---8----4----2-----1

1----0----0----0----1-----1

I will go bit by bit now

  • Bit index 1 is turned on, so I have 1!
  • Bit index 2 is turned on, so I have 2!
  • Bit index 3 is turned off, skip!
  • Bit index 4 is turned off, skip!
  • Bit index 5 is turned off, skip!
  • Bit index 6 is turned on, I have 32!

Result: 1 + 2 + 32 = 35

Hope this helps! :)

Upvotes: 2

Gassa
Gassa

Reputation: 8846

In a modern computer, integers are already represented in binary. You can take advantage of that by using bitwise operations (pseudocode):

for p := 30 downto 0:
    if (x and (1 shl p)) > 0:
        output (1 shl p)

For example, given x = 10010 = 11001002, the program will output 64, 32 and 4.

Here, shl is a shift operation and and is bitwise AND.

Upvotes: 1

AndyG
AndyG

Reputation: 41090

You could continue taking the log base 2 of the number until you reach a number evenly divisible by 2^(log base 2 of that number)

Example:

  • 1536
  • log_2(1536) = 10 (so, add 210 = 1024 to your list)
  • remainder = 1536 - 1024 = 512
  • log_2(512) = 9 (so, add 29 = 512 to your list)
  • remainder = 512 - 512 = 0
  • so your list contains 1024 and 512

Working Python:

import math
goal = int(raw_input("Enter a goal"))
solution = []
while(goal > 0):
    nextExponent = int(math.log(goal)/math.log(2))
    goal -= 2**nextExponent
    solution.append(2**nextExponent)
print solution

If your set of powers of 2 is limited, you will have to cap nextExponent at the maximum.

Sample input:

Enter a goal 58094

Output:

[32768, 16384, 8192, 512, 128, 64, 32, 8, 4, 2]

Upvotes: 0

Related Questions