Wonderful work as usual. I tried out a bit manipulation approach where I ensure there's only one set bit (which ensures its a power of 2) and only an even number of 0 bits to the right of that set bit (ensuring its a power of four). Runtime is O(32) and since the number of bits is independent of the size of n, it is constant time. The memory used doesn't grow based on n either so space complexity is also O(1). To anyone reading this, please let me know if I'm mistaken! : class Solution: def isPowerOfFour(self, n: int) -> bool: ones,zeros = 0,0 scanning_zeros = True for i in range(32): bit = 1 & (n >> i) if bit == 1: ones+=1 scanning_zeros = False else: if scanning_zeros: zeros += 1 # print(ones,zeros) return (ones == 1 and zeros % 2 == 0)
There actually are only 16 powers of 4 in the given range, so another very simple and efficient solution is to simply check all of them, e.g. generate a set or list of them beforehand (for me, a list was more efficient, since hashing is more overhead than simply checking all the elements in the list). Depending on the language, hard-coding the branches might be even faster. One could even hard code a binary search on it. Although the solution using bits that somebody else posted in the comments can probably be implemented with just a few assembly instructions using stuff like popcnt which probably is even faster.
At first I want to solve this with a simple for loop or recursion, but soon I saw the follow up of this question by asking me not to use loop or recursion...... it recalled my high school mathematics using logarithm to check if x is an int, so here's my solution: idea: n == 4^x log n = x log 4 log n/log 4 = n Rest is just check if n is an int, but the calculation could return a float even the value is in fact an integer. Thus, here's my code: if(n
Also has constant time solution running cycle up to 16 times and shifting bits and comparing with the number. Rust solution impl Solution { pub fn is_power_of_four(mut n: i32) -> bool { if n < 0 || n.count_ones() > 1 { // don't remember why i popcntd them return false } let mut x = 0; for i in (0..32).step_by(2) { let o = (1
if you had a function inside the isPowerOfFour function you could have called it without self. but since you are calling the same function , you have to use self.
this is my solution that works with bits if n==1: return 1 if n>1 i+=1 print(pos,cnt) return not pos&1!=0 and cnt==1 intuition is all even powers of 2 are powers of 4
that was the solution i was hoping to see we can check if is a power of two by evaluting n & (n - 1) == 0 then lets define def isPowTwo(x): n & (n - 1) == 0 if a number is of power of two and it's half is also a power of two then it's definitely a power of four so return isPowTwo(x) && isPowTwo(x>>1)
I think every number which is power of 2 and whose half is power of 2 Will not be a power of 4 Eg:8 Instead it is better to check if it's a even power of 2
Wonderful work as usual. I tried out a bit manipulation approach where I ensure there's only one set bit (which ensures its a power of 2) and only an even number of 0 bits to the right of that set bit (ensuring its a power of four). Runtime is O(32) and since the number of bits is independent of the size of n, it is constant time. The memory used doesn't grow based on n either so space complexity is also O(1). To anyone reading this, please let me know if I'm mistaken! :
class Solution:
def isPowerOfFour(self, n: int) -> bool:
ones,zeros = 0,0
scanning_zeros = True
for i in range(32):
bit = 1 & (n >> i)
if bit == 1:
ones+=1
scanning_zeros = False
else:
if scanning_zeros:
zeros += 1
# print(ones,zeros)
return (ones == 1 and zeros % 2 == 0)
My solution O(1) time complexity:class Solution {
public:
bool isPowerOfFour(int n) {
if(n==0){
return false;
}
return ceil(log(n)/log(4)) == floor(log(n)/log(4));
}
};
There actually are only 16 powers of 4 in the given range, so another very simple and efficient solution is to simply check all of them, e.g. generate a set or list of them beforehand (for me, a list was more efficient, since hashing is more overhead than simply checking all the elements in the list). Depending on the language, hard-coding the branches might be even faster. One could even hard code a binary search on it. Although the solution using bits that somebody else posted in the comments can probably be implemented with just a few assembly instructions using stuff like popcnt which probably is even faster.
that is indeed efficient. constant time and memory
At first I want to solve this with a simple for loop or recursion, but soon I saw the follow up of this question by asking me not to use loop or recursion...... it recalled my high school mathematics using logarithm to check if x is an int, so here's my solution:
idea:
n == 4^x
log n = x log 4
log n/log 4 = n
Rest is just check if n is an int, but the calculation could return a float even the value is in fact an integer.
Thus, here's my code:
if(n
while n > 1:
if n % 4: return False
n //= 4
return True
you are a legend
Thanks for the leetcode daily !
Easy straightforward solution:
return n and not (n & (n - 1)) and n & 0x55555555
People should also check out the solutions for power of two and power of three.
How is about binary search?
Also has constant time solution running cycle up to 16 times and shifting bits and comparing with the number.
Rust solution
impl Solution {
pub fn is_power_of_four(mut n: i32) -> bool {
if n < 0 || n.count_ones() > 1 { // don't remember why i popcntd them
return false
}
let mut x = 0;
for i in (0..32).step_by(2) {
let o = (1
We can use log here
If log(n) base 4 in an integer then true
Tabs or spaces?
Amazing!
Could you explain what that self.function name is? Couldn't we just call rhe function ordinarily
it's how you call a function that exists within the same class where you're calling it in Python.
refering to the class(Solution) instance's method (function name)
if you had a function inside the isPowerOfFour function you could have called it without self. but since you are calling the same function , you have to use self.
Learn Python OOPS basics , that way you will understand things better , will take 1-2 hours
Every power of 4 => is power of 2 && 3x+1 form
oh yay, finally an easy problem... *_struggles_*
Can you do it with bits ?
this is my solution that works with bits
if n==1:
return 1
if n>1
i+=1
print(pos,cnt)
return not pos&1!=0 and cnt==1
intuition is all even powers of 2 are powers of 4
Here is simple JAVA CODE
class Solution {
public boolean isPowerOfFour(int n) {
for(int i=0;i
that was the solution i was hoping to see
we can check if is a power of two by evaluting n & (n - 1) == 0
then lets define def isPowTwo(x): n & (n - 1) == 0
if a number is of power of two and it's half is also a power of two then it's definitely a power of four
so return isPowTwo(x) && isPowTwo(x>>1)
I think every number which is power of 2 and whose half is power of 2
Will not be a power of 4
Eg:8
Instead it is better to check if it's a even power of 2
@@628sonu That's not true at all. Every power of two divided by two is still a power of two and they obviously aren't all powers of 4.
❤
Even though i am getting hint my rusty brain not functioning 😭😭😔😔😢😢