CODEWITHSUNDEEP
pythonpython-3.x
KimHee
KimHee

Reputation: 788

How to find highest power of 2 less than n in a list?

I have a list likes

lst = [20, 40, 110]

I want to find the highest power of 2 in the list satisfied as

For the first number, the highest power of 2 will get the first element of the list as input. So the result is 16 (closest to 20)

For the next numbers, it will get the summation of previous result (i.e 16) and current number (.i.e 40) so the closest number will be 32 (closest 40 +16)

So the output what I expect is

lst_pow2 = [16, 32, 128]

This is my current code to find the highest number of a number, but for my problem it should change something because my input is list. Any suggestion? Thanks

# Python3 program to find highest  
# power of 2 smaller than or  
# equal to n. 
import math 
  
def highestPowerof2(n): 
  
    p = int(math.log(n, 2)); 
    return int(pow(2, p));

So what I tried but it does not do the summation

lst_power2 = [highestPowerof2(lst[i]) for i in range(len(lst))]

Upvotes: 1

Views: 730

Answers (5)

tevemadar
tevemadar

Reputation: 13245

You could use reduce() too:

functools.reduce(lambda res,n:res+[highestPowerof2(n+res[-1])],lst,[0])[1:]

which is short, just the [1:] is ugly at the end
Or as:

functools.reduce(lambda res,n:res+[highestPowerof2(n+(len(res) and res[-1]))],lst,[])

which does not need the slicing, but it is less readable inside.

Full example:

import math,functools

def highestPowerof2(n):
    p = int(math.log(n, 2))
    return int(pow(2, p))

lst = [20, 40, 110]
print(functools.reduce(lambda res,n:res+[highestPowerof2(n+res[-1])],lst,[0])[1:])
print(functools.reduce(lambda res,n:res+[highestPowerof2(n+(len(res) and res[-1]))],lst,[]))

Upvotes: 1

Error - Syntactical Remorse
Error - Syntactical Remorse

Reputation: 7897

This question has an accepted answer but I thought this would be a good problem that could also be solved by using a generator. The accepted answer is definitely compact but I though it would be fun to give this solution as well.

lst = [20, 40, 110]

import math 

def highestPowerof2(lst): 
    last = 0
    for element in lst:
      p = int(math.log(element + last, 2))
      last = int(pow(2, p)) # Remember the last value
      yield last

lst_power2 = [i for i in highestPowerof2(lst)]
print(lst_power2)

Upvotes: 1

perennial_noob
perennial_noob

Reputation: 468

You may want to modify your approach thus:

  1. Modify your function to take 2 integers. prev_power and curr_num (this was n in your code)
  2. Calculate the power of 2 for the first number and add to a result list
  3. Now pass this number and the next number in the list to your highestPowerof2 function

Upvotes: 2

Gautam
Gautam

Reputation: 1932

You can perhaps use the following : 

lst_power2 = [highestPowerof2(lst[i]+((i>0) and highestPowerof2(lst[i-1]))) for i in range(len(lst))]

instead of 

lst_power2 = [highestPowerof2(lst[i]) for i in range(len(lst))]

Upvotes: 2

Paritosh Singh
Paritosh Singh

Reputation: 6246

Use an extra variable that keeps track of the value to be added, and build your logic while iterating.

lst = [20, 40, 110]

import math 

def highestPowerof2(n): 
    p = int(math.log(n, 2)) #you do not need semi colons in python
    return int(pow(2, p))

acc = 0 #to keep track of what was the last highest* power
result = []
for n in lst:
    result.append(highestPowerof2(n + acc))
    acc = result[-1]

print(result)
#Output:
[16, 32, 128]

Upvotes: 1

Related Questions