# Challenge 3: Power of 2

We solve by making use of the & operator in computers. There are many ways to solve this, of which two approaches are simple, and one is a more complex but better solution.

In this lesson, we will try to check if the given number is a power of 2. We solve this by writing an efficient algorithm that takes an optimal amount of time.

### Introduction

Let’s do another challenging question to check your understanding of Bitwise operators.

## Example:

``````Input: 4

Output: True (As 4 is 2^2)``````
``````Input: 12

Output: False``````

## Problem statement

Write a program to check whether a given number is a power of 2.

Let’s consider a number and find how the AND (`&`) operator does this.

``````Input = 64

Output: True``````

Explanation: We solve by making use of the `&` operator in computers. There are many ways to solve this, of which two approaches are simple, and one is a more complex but better solution.

Assume n is non-negative. Use the & operator to achieve this.

## Brute-force/naive approach

Hint: The exciting part of calculating the power of 2 is that they have a set-bit count equal to one.

### Algorithm

• Repeatedly divide input with `2`.
• if `n` not equal to `1` and if it is odd, we will return `false`.
• else `true`.

Here is what our algorithm will look like:

### Solutions

#### Java

``````class IsPowerOf2 {
private static boolean helper(int n) {
if (n == 0) {
return false;
}

while (n != 1) {
if (n % 2 != 0) {
return false;
}
n >>= 1;
}
return true;
}

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

#### Python

``````def IsPowerOf2(n):
if n == 0:
return False
while n != 1:
if n %2 !=0:
return False
n >>= 1
return True

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

#### JavaScript

``````const IsPowerOf2 = number => {

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

while (n !== 1) {
if(n % 2 !== 0) {
return false;
}
n >>= 1;
}
return true;
}

return helper (number);
}

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

#### C++

``````#include <iostream>

using namespace std;

bool helper(int n) {
if (n == 0) {
return false;
}
while (n != 1) {
if (n % 2 != 0) {
return false;
}
n >>= 1;
}
return true;
}

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;
}

while (value !== 1) {
if (value % 2 !== 0) {
return false;
}
value >>= 1;
}
return true;
}

return helper(n);
}

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

### Complexity analysis

#### Time complexity

This takes `log(n)` complexity. We can do better in constant time using Brian Kernighan’s algorithm.

#### Space complexity

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

## Coding exercise

Now, try to optimize the above solution/algorithm. There is a better way to solve this problem.

This problem is designed for your practice, so try to solve it yourself first. If you get stuck, you can always refer to the solution in the next lesson. Good luck!

Hint: Learn about "Brian Kernighan’s algorithm", because in next solution review, we are about to solve this with his approach.

First, look at these code snippets below and think of a solution.

``````// Java
// TODO: finish the challenge or check next lesson for solution
class Solution{
public static boolean isPow2(int n){
// Write - Your - Code- Here

return false; // change this, return true/false based on inputs
}
}``````
``````# Python
# TODO: finish the challenge or check next lesson for solution
def Solution(n):
# Write - Your - Code- Here

return False # change this, return True/False based on inputs
``````
``````// JavaScript
// TODO: finish the challenge or check next lesson for solution
const isPow2 = n => {
// Write - Your - Code- Here

return false; // change this, return true/false based on inputs
}``````
``````// C++
// TODO: finish the challenge or check next lesson for solution
#include <iostream>
#include <string>
using namespace std;

bool isPowerOfTwo(int n) {
// Write - Your - Code- Here

return false; // change this, return true/false based on inputs
}``````
``````// TypeScript
// TODO: finish the challenge or check next lesson for solution
export const isPow2 = (n: number): boolean => {
// Write - Your - Code- Here

return false; // change this, return true/false based on inputs
}``````

The solution will be explained in the next lesson.

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