# Solution Review: Power of 2

Let's solve this using brain kernighan's algorithm. This is optimized to O(1) time and space.

Let's see how we use Brain Kernighan's algorithm to achieve this.

## Solution review: Brian Kernighan’s algorithm

We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this more efficiently using Briann’s Algorithm.

In this approach, we count the set bits. If a number is the power of 2, we know that only one set bit is present in its Binary representation.

In binary, we go from right to left with powers of 2.

For example:

20, 21, 22, 23, 24, and so on...

## Algorithm

Before we talk about algorithmic steps, you should review the table data and slider shown below the table.

• if `(n & (n - 1) == 0)`, return `true`
• else, `false`

Let’s visualize the values in the table below:

n n (in binary) (n - 1) (n - 1) in binary n & (n - 1) (n & (n - 1) == 0)
2 0010 (2 - 1) = 1 0001 (2 & 1) = 0 true
6 0110 (6 - 1) = 5 0101 (6 & 5) = 4 false
8 1000 (8 - 1) = 7 0111 (8 & 7) = 0 true
10 1010 (10 - 1) = 9 1001 (10 & 9) = 8 false

Let’s see a couple of examples:

``````        n   = 4    => 00000000 00000000 00000000 00000100
n - 1 = 3    => 00000000 00000000 00000000 00000011
-----------------------------------------------------------
(n & (n - 1)) = 0  => 00000000 00000000 00000000 00000000
-----------------------------------------------------------``````

`( n & (n - 1))`, here this becomes `0`, which is true. Hence, the number `4` is a power of 2.

``````        n   = 6    => 00000000 00000000 00000000 00000110
n - 1 = 5    => 00000000 00000000 00000000 00000101
-----------------------------------------------------------
(n & (n - 1)) = 4  => 00000000 00000000 00000000 00000100
-----------------------------------------------------------``````

`( n & (n - 1))` is `4`, which is not equal to `0`. Hence, the number `6` is not a power of 2.

## Solution

Here is the reasoning behind this solution.

### Java

``````class IsPowerOf2 {
public static void main(String[] args) {
System.out.println(helper(6));
System.out.println(helper(8));
}

/**
* Return boolean(even/odd) for the given number.
*
* @param n
* @return
*/
private static boolean helper(int n) {
if (n == 0) {
return false;
}
return (n & (n - 1)) == 0;
}
}``````

We can further simplify this code into a single line shown below.

``````class IsPowerOf2 {
public static void main(String[] args) {
System.out.println(helper(6));
System.out.println(helper(8));
}

/**
* Return boolean(even/odd) for the given number.
*
* @param n
* @return
*/
private static boolean helper(int n) {
return n != 0 && (n & (n - 1)) == 0;
}
}``````

### Python

``````def helper(n):
if n == 0:
return False
return (n & (n - 1) == 0)

print(helper(6))
print(helper(8))``````

We can further simplify this code into a single line shown below.

``````def IsPowerOf2(n):
return n != 0 and (n & (n - 1)==0)

print(IsPowerOf2(6))
print(IsPowerOf2(8))``````

### JavaScript

``````/**
* Return boolean(even/odd) for the given number.
*
* @param {number} number
* @return {boolean}
*/
const IsPowerOf2 = number => {

function helper (n) {
if(n === 0) {
return false;
}
return (n & (n - 1)) === 0;
}

return helper (number);
}

console.log (IsPowerOf2 (6));
console.log (IsPowerOf2 (8));
``````

We can further simplify this code into a single line shown below.

``````/**
* Return boolean(even/odd) for the given number.
*
* @param {number} number
* @return {boolean}
*/
const IsPowerOf2 = n => {
return n !== 0 && (n & (n - 1)) === 0;
}

console.log (IsPowerOf2 (6));
console.log (IsPowerOf2 (8));
``````

### C++

``````#include <iostream>

using namespace std;

bool helper(int n) {
if (n == 0) {
return false;//0 represents as false and 1 represents as true.
}
return (n & (n - 1)) == 0;
}

int main() {
cout << helper(6) << endl;
cout << helper(8) << endl;
return 0;
}``````

We can further simplify this code into a single line shown below.

``````#include <iostream>

using namespace std;

bool helper(int n) {
return n != 0 && (n & (n - 1)) == 0;
}

int main() {
cout << helper(6) << endl;
cout << helper(8) << endl;
return 0;
}``````

### TypeScript

``````export const IsPowerOf2 = (n: number): boolean => {
function helper(value: number): boolean {
if (value === 0) {
return false;
}
return (value & (value - 1)) === 0;
}

return helper(n);
}

console.log(IsPowerOf2(6));
console.log(IsPowerOf2(8));
``````

We can further simplify this code into a single line shown below.

``````const IsPowerOf2 = (n: number): boolean => {
return n !== 0 && (n & (n - 1)) === 0;
}

console.log (IsPowerOf2 (6));
console.log (IsPowerOf2 (8));``````

## Complexity analysis

Time complexity: `O(1)`

The run time depends on the number of 1-bits in n. In the worst case, all bits in n are 1-bits. In the case of a 32-bit integer, the run time is `O(1)`.

Space complexity: `O(1)`

The space complexity is `O(1)`. No additional space is allocated.

Coding Interview QuestionsData Structures and AlgorithmsBit Manipulation

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things