LeetCode's challenge of the day on June 8, 2020 (#231) asks us to write a function that determines if the given Integer n
is a power of two. In other words: If we multiply the number 2 any amount of times, will we end up with n
?
This is a typical dynamic programming problem. We could solve it with recursion. Using a helper function, we would pass n
and the current
multiplication. But, if n
is large enough, the function would be called thousands of times and we might run into stack overflow
protection and get a Segment 11
error code.
Bottom Up Approach
The approach we will use is called the Bottom Up Approach. The idea is that we are utilizing a dp
array. "dp" stands for dynamic programming and naming the array dp
is a convention widely used in tech challenges and interviews.
1) 2^0
is explained in the examples as n = 1
and 2^1
is logically 2
. Those are our exit conditions.
2) Based on the exit condition in 1), 2 is the last value we have processed ( 2^1
).
3) Since we don't know how many multiples we will need to end up at n
, we're using a for loop from 2 up to Int.max
4) First, within the loop we will get the last processed number and multiply it by 2 to get the current number.
5) Then, we are checking if current
equals the given number n
. If so, return true.
6) If the current number is larger than n
, we know that n
is not a power of two and we need to return false.
7) Update the last element using the current one and continue the loop.
8) Lastly, we return false to satisfy the compiler.
Time and space complexity
The time complexity is expressed as O(n)
where n
is the possible multiples between 0
and the given integer n
. The space complexity is linear as we're only storing the last processed variable.
New article πβΊοΈ
— David Seek (@DavidSeek) February 2, 2021
This one has been sitting on draft for a while. I'm talking about my past, my career and how I got into FAANG.
Less technical, and more personal.
Retweet and like for reach highly appreciated π₯°https://t.co/EWskDl5Jmm