342. Power of Four
Problem Description
The problem is to identify whether a given integer n is a power of four. That is, we need to determine if there exists an integer x such that when 4 is raised to the power x (4^x), the result is n. This determination must result in a boolean value of either true if n is indeed a power of four or false if it is not.
Intuition
The intuition behind the solution to this problem comes from understanding the properties of numbers that are powers of four:
-
Greater than zero: A power of four must be a positive integer because raising four to any power yields a positive result.
-
Unique bit pattern: Powers of four in binary representation have a unique pattern. They have one and only one bit set (1), and the number of zeros following this bit is even. For example, 4 in binary is
100, and 16 is10000. -
Checking single bit: To check for the single bit pattern, a common technique is to use the bitwise AND operation with
nandn - 1. Ifnis a power of two (which is a subset condition for being a power of four), thenn & (n - 1)will be zero because there will be only one '1' in the binary representation ofn. -
Differentiating power of four from power of two: Simply being a power of two does not guarantee that a number is a power of four. To differentiate, we notice that the only '1' bit in a power of four is at an even position, counting from right (starting at 1). One way to check this is to use a bitmask. The bitmask
0xAAAAAAAAcontains '1's in the odd positions of a 32-bit number, which will never overlap with a power of four. Therefore, the condition(n & 0xAAAAAAAA) == 0must hold true for powers of four, ensuring the only '1' bit is in the correct position.
Putting these checks together gives us a concise way to determine if n is a power of four. Therefore, the solution uses a composite condition: n > 0 (positive check) and (n & (n - 1)) == 0 (single bit check) and (n & 0xAAAAAAAA) == 0 (correct bit position check) to verify if n is a power of four.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Solution Approach
The solution provided uses bitwise operators to efficiently determine if a given integer n is a power of four. Here's the step-by-step implementation approach:
-
Positive check: We first check if
nis greater than zero since a power of four cannot be zero or negative. This is simply checked usingn > 0. -
Power of two check: Next, we want to confirm if the number is a power of two. This property is required since all powers of four are also powers of two (but not all powers of two are powers of four). The bitwise operation
n & (n - 1)is used to determine this. For numbers that are powers of two, there is precisely one '1' in their binary representation. Subtracting one from such a number changes the rightmost '1' to '0' and all the bits to the right of it to '1's. When we perform an AND operation between such a number and its predecessor (which has a '0' in that position and '1's after), the result will be zero. So(n & (n - 1)) == 0must be true for powers of two. -
Power of four check: To ensure that
nis not just a power of two but specifically a power of four, another condition must be verified. In binary terms, the single '1' bit of a power of four appears only in even positions (1-indexed). To test this, a bitmask0xAAAAAAAAis created, where all the odd positions have a '1' (when counting from right and starting from zero). Ifnis a power of four, ANDing it with this bitmask should yield zero, since its only '1' should be in an even position and hence not overlap with the '1's in the bitmask. Thus, we need(n & 0xAAAAAAAA) == 0to be true as well.
The combination of these three checks (n > 0), (n & (n - 1)) == 0, and (n & 0xAAAAAAAA) == 0, used in a single return statement with logical ANDs, ensures that we only return true if all conditions are satisfied, confirming n is a power of four.
The efficiency of this approach comes from using bitwise operations, which are very fast and allow us to avoid expensive computations like loops or recursion that might be used in alternative solutions.
What are the most two important steps in writing a depth first search function? (Select 2)
Example Walkthrough
Let's walk through the solution approach using the example where n = 64.
First, we want to verify if 64 is greater than zero. Since 64 > 0 is true, we pass the first check.
Next, to check if 64 is a power of two, we use the "power of two check" by computing 64 & (64 - 1). The binary representation of 64 is 1000000 and the binary for 63 is 111111, so:
64 (in binary): 1000000
63 (in binary): 0111111
----------------AND
Result : 0000000
Since the result is zero, 64 is confirmed to be a power of two, satisfying the second condition.
Finally, we must verify if 64 is specifically a power of four. For this, we check if the only '1' bit in 64 is in an even position, using the "power of four check" with the bitmask 0xAAAAAAAA. This bitmask in binary is 10101010101010101010101010101010. Performing an AND operation between 64 and 0xAAAAAAAA:
64 (in binary) : 00000000000000000000000001000000
0xAAAAAAAA (in binary): 10101010101010101010101010101010
-----------------------------------------------------AND
Result : 00000000000000000000000000000000
Since the result is zero, the '1' is at an even position (the sixth position from right, 1-indexed), fulfilling the last condition.
Because all three conditions pass:
n > 0(n & (n - 1)) == 0(n & 0xAAAAAAAA) == 0
We conclude that 64 is indeed a power of four and the final evaluation will correctly return true.
Solution Implementation
1class Solution:
2 def is_power_of_four(self, num):
3 """
4 Check if a number is a power of four.
5
6 The method applies bitwise operations to determine if the number is a power of four.
7 This is done in two steps:
8 1. Check if the number is greater than zero.
9 2. Confirm that the number is a power of two by checking whether it has only one bit set.
10 This is done by ensuring that the number has no bits in common with its predecessor (num & (num - 1)) == 0.
11 3. Check that the single bit is in the correct position for a power of four ((num & 0xAAAAAAAA) == 0).
12
13 :param num: integer, the number to check
14 :return: boolean, True if num is a power of four, False otherwise
15 """
16
17 # 0xAAAAAAAA is a hexadecimal number with a pattern where all even bits (starting from the least significant bit) are set,
18 # which are not set for powers of four. In other words, when the bit of the power-of-four number is at an even position,
19 # it should not intersect with the 0xAAAAAAAA mask.
20
21 # First condition: num should be positive.
22 # Second condition: there should only be a single bit set in num.
23 # Third condition: the bit must not be in a position that would intersect with 0xAAAAAAAA.
24 return num > 0 and (num & (num - 1)) == 0 and (num & 0xAAAAAAAA) == 0
25
26# This would be used as follows:
27# sol = Solution()
28# result = sol.is_power_of_four(16)
29# print(result) # This would print True, since 16 is indeed a power of four (4^2)
301class Solution {
2
3 /* Function to check if a given number is a power of four */
4 public boolean isPowerOfFour(int num) {
5 // First, check if 'num' is positive since powers of four are always positive.
6 // Then, check if 'num' is a power of two by confirming that only one bit is set in its binary representation.
7 // This is done by using the bitwise AND operation between 'num' and 'num - 1', which should equal zero.
8 // Finally, check if the only set bit is in the correct position to represent a power of four.
9 // This is done by using bitwise AND with the hex value 0xAAAAAAAA, which has set bits at the positions
10 // corresponding to the powers of two but not four. If 'num' is a power of four, this result should be zero.
11
12 return num > 0 && (num & (num - 1)) == 0 && (num & 0xAAAAAAAA) == 0;
13 }
14}
151class Solution {
2public:
3 bool isPowerOfFour(int num) {
4 // Check if num is greater than 0, because powers of 4 are positive numbers.
5 // Also check if num is a power of 2 by ensuring it has only one bit set using (num & (num - 1)) == 0.
6 // Finally check if the set bit is in the correct place for a power of 4 by checking that none
7 // of the bits in the odd positions are set using (num & 0xAAAAAAAA) == 0.
8 // 0xAAAAAAAA is a hexadecimal constant which has 1s in the odd positions and 0s in the even positions.
9
10 return num > 0 && (num & (num - 1)) == 0 && (num & 0xAAAAAAAA) == 0;
11 }
12};
131function isPowerOfFour(n: number): boolean {
2 // Check if 'n' is greater than 0 because powers of four must be positive.
3 // The expression 'n & (n - 1)) == 0' checks if 'n' is a power of 2
4 // because only powers of 2 have a single bit set in binary.
5 // But since we are interested in powers of 4, we need another check.
6 // The number must not have bits set in places that would indicate it's also a power of 2 but not a power of 4.
7 // In binary, powers of 4 are of the form 1 followed by an even number of 0s.
8 // The mask '0xaaaaaaaa' has 1s in the odd positions (starting from 1).
9 // By &-ing it with 'n' and checking for 0, we are ensuring 'n' has 1s only in even positions – i.e., it's a power of 4.
10 return n > 0 && (n & (n - 1)) === 0 && (n & 0xaaaaaaaa) === 0;
11}
12Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?
Time and Space Complexity
The time complexity of the function isPowerOfFour is O(1), which means it runs in constant time. This is because it only involves a finite number of bitwise operations and comparisons, which do not depend on the size of the input number n.
The space complexity of the function isPowerOfFour is also O(1), indicating that it uses a constant amount of space. The amount of memory used does not increase with the input size as it only requires space for a fixed number of variables to process the operations.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.