Power of Two, A Google Interview Question - C++ Solution
Tags: bitwise, cpp, algorithms, faang
Published: 2022-02-21 16:42:03

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 01:**

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

**Example 02:**
```javascript
Input: 12
 
Output: False
```

## Problem statement
Write a program to check if a given number is a power of 2 or not.

Let’s consider a number and find how the AND operator does this.

```javascript
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 of them is a more complex but better solution.


> Assume `n` is non-negative. We use the `&` operator to achieve this.

## Solution: Brute-force/naive approach

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

## Algorithm

1. Read the input value.

2. 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:

```cpp
#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;
}
```

## Complexity Analysis

**Time complexity:** `O(logn)`

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

**Space complexity:** `O(1)`

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

## Coding Exercise
First, take a close look at the code snippets above and think of a solution. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the solution provided in the solution section. Good luck!

```cpp
#include <iostream>
#include <string>
using namespace std;

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

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

If you've got the answer great! if not, its normal, practice similar problems and you'll get a good hold of bit manipulation tricks.

The solution will be explained in below.

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

## Solution review: Brian Kernighan’s algorithm

This is considered faster than the previous naive approach.

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:
> 2^0, 2^1, 2^2, 2^3, 2^4, and so on.

## Algorithm
Before we talk about algorithmic steps, you should review the tabular form of steps that depicts the algorithm.

1. If `(n & (n - 1) == 0)`, return `True`.

2. else, `False`.

Let’s visualize the values in the table below:

![Power Of 2 algorithm in tabular format](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ukkey12yztqg06o149is.png)

Let’s see a couple of examples:

```java
        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.

```java
        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.

Let us take a look at the optimized approach.

## Code
Here is the reasoning behind this solution.

```cpp
#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.

```cpp
#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;
}
```

## 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.

---

## Extras

If you are interested in mastering bit tricks, I've got a course that are loved by more than 100k+ programmers. 

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. The course has simple explanation with sketches, detailed step-by-step drawings, and various ways to solve it using bitwise operators. 

These bit-tricks could help in competitive programming and coding interviews in running algorithms mostly in `O(1)` time.

This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG(Facebook, Amazon, Apple, Netflix, and Google) companies.

To kick things off, you’ll start by learning about the number system and how it’s represented. Then you’ll move on to learn about the six different bitwise operators: AND, OR, NOT, XOR, and bit shifting. Throughout, you will get tons of hands-on experience working through practice problems to help sharpen your understanding.

By the time you’ve completed this course, you will be able to solve problems faster with greater efficiency!! 🤩

Link to my course: [Master Bit Manipulation for Coding Interviews](https://www.educative.io/courses/bit-manipulation?aff=xjzd).