Power of Two - Leetcode 231 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/power-o...
0:00 - Read the problem
0:10 - Drawing Explanation
2:00 - Coding Explanation
4:21 - Drawing Explanation
7:33 - Coding Explanation
8:50 - Drawing Explanation
11:41 - Coding Explanation
leetcode 231
#neetcode #leetcode #python

[@edmonddantes587]

it's worth studying bit manipulation. Not really that tricky (I'm dumb and can understand it), and feels good when you solve problems like this.

[@edis671games]

cool info about bit operations

[@user-tg6jl2nz7o]

another similar solution: return n > 0 and n == (n & -n)

[@piotrwszoek9387]

I'm new to code katas and python in general: Why not just: return n > 0 and math.log2(n).is_integer()? Using built-in libraries is forbidden during code interviews? I know it's probably not the fastest and clearest solution but I think it is still easier to get then bitwise operations. Thank you!

[@user-kw5hm7fq5m]

What about a binary search solution For example 2 ^ x = 16 We will calculate all the possible values to x is between 0 & 16 and by using binary search. we will get the mid check if 2 ^ mid is greater or smaller or equal

[@shenawy04]

This is a bit more intuitive I think. class Solution: def isPowerOfTwo(self, n: int) -> bool: if n

[@anon_y_mousse]

I personally prefer the subtractive method because not every processor has divide, and divide is slower anyway even when available.

[@jshaikh3897]

Hi all, I came up with the following solution when I was trying for a brute force approach. Apologies if this sounds silly but Is this good or bad brute force approach to come up with, while interviewing : class Solution: def isPowerOfTwo(self, n: int) -> bool: # base case: if n==1: return True # check if n is odd or less than 1 or check if n has more than one bits set to 1 if ((n%2)!=0) or n

[@ecchioni]

Funny how the fastest solution for me was a loop.

[@DeathSugar]

Coz under hood it could optimize out your loop to popcnt instruction which makes your loop hardware accelerated.

[@ecchioni]

@@DeathSugar Yes, I know that. The moral of the story, don't try to be too clever.

[@satyamjha68]

A one liner problem!! I am actually unable to solve hard questions with acceptance rete less than 60%. Do you have any tips on how I can improve?

[@SairamDasari2000]

Practice Practice.... That's it

[@axaide4210]

Practice as much as you can

[@Munchen888]

Even if you can’t pass the task don’t use chat gpt. If you don’t bring the task to end you are sure that you tried to solve YOURSELF.

[@satyamjha68]

@@Munchen888 I never use gpt for dsa. Even I am unable to solve it like after an hour or 2 , I try to see hints. If I am still unable to solve the problem , I look at the solution. Is this approach fine?

[@suhasnadiga]

Didn't spend more than 30 mins

[@MarriRahul]

similar answer: if n

[@dingus2332]

You can achieve the answer by left shift as well -> class Solution: def isPowerOfTwo(self, n: int) -> bool: for i in range(32): ans = 1

[@MehmetDemir-xi3yy]

I couldn't get it the constant time explanation. How it is constant time even if it is integer max value? If so let's say when we do linear search in list which has size of int max value, can we say it is constant time?

[@MehmetDemir-xi3yy]

Btw, I am referring the first solution which uses loop. It will iterate logn times as you said.

[@NeetCodeIO]

Technically the if input n is no larger than 2^32 so its O(32) = O(1). In theory, if the input isnt bounded it's O(logn). I guess O(logn) is the more correct time complexity.

[@MehmetDemir-xi3yy]

So I guess you said it for in practical terms and it makes really sense. Don't get me wrong I am just trying to understand correctly not trying to be smart mouth. I understood it will iterate max 32 times(ish) but it is still bounded to N even if they are small numbers because we will log it. It may iterate 4 or 16 times according to n as you know.

[@NeetCodeIO]

@@MehmetDemir-xi3yy no worries, i think you're right that btw

[@leeroymlg4692]

@@MehmetDemir-xi3yy it's technically O(logn). Since the time complexity does scale as the input size increases. But we know worst case it won't iterate more than 30 times. So it can be thought of as 0(30) since big O does focus on the worst case performance This function below is slower but it's 0(1) because it's guaranteed to loop 30 times regardless of n. powers = [1] p = 1 for i in range(30): p *= 2 powers.append(p) return True if n in powers else False

[@StephenRoseDuo]

My solution is 99th percentile and uses sets

[@kartikeysaini7272]

should i quit programming I think my solution is shit: class Solution: def isPowerOfTwo(self, n: int) -> bool: l=[] for i in range(0,100): l.append(2**i) for i in range(0,len(l)): if n == l[i]: return True else: return False

[@MohanRaj-vp1zt]

Mathematically, even -1 is an integer.

[@NeetCodeIO]

Yes that's right. I don't think i stated otherwise anywhere in the video.

[@MohanRaj-vp1zt]

@@NeetCodeIO : Thanks for your prompt reply :) . But you said - "We are told, that we given integers only, so we don't worry about negative exponents."

[@driss9949]

@@MohanRaj-vp1zt and what does -1 have to do with a negative exponent ?

[@lakshaybansal2470]

return n > 0 && (__builtin_popcount(n) == 1);