Skip to content

Power Of Two (Exercise Problem)

This is an exercise problem for your practice. Try to come up with an approach and solve it by yourself. Good Luck!

Gopi Gorantala
Gopi Gorantala
3 min read

Create Functional Interface

Let us see an example by creating our own functional interface and doing some checks with the given data.

Problem Statement

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

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. Use the & operator to achieve this.

Algorithm

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

Here is what our algorithm will look like:

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

Wait! Is this a better approach? an optimized solution? Nope, can we do better?

Yes, we can do better using the Bit Manipulation technique & operator. Let us see the following code which is optimized and takes O(1) time complexity and O(1) space complexity.

Let us try to implement our own functional interface with the problem given using a lambda expression.

If you do not understand the following example, that’s totally normal. We will dive more into lambda expressions in the next lessons.

For now, here are some notes for your understanding.

Optimized Solution: 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:

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

Basics Of AND Operator (&)

The Bitwise AND operator is denoted by &. When an AND gate is given with two inputs, the corresponding output will be:

  • If two input bits are 1, the output is 1.
  • In all other cases its 0, for example
    • 1 & 0 => yields to 0.
    • 0 & 1 => yields to 0.
    • 0 & 0 => yields to 0.

Brian Kernighan’s algorithm 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:

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.

Coding exercise

// DEFINE-YOUR-OWN FUNCTIONAL-INTERFACE
// WRITE-A-METHOD-THAT-RUNS-THE-EXECUTION

Now, try to come up with an approach. 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 below. Good luck!

Hint: Read the functional interface declaration and implementations in previous lessons to implement this.

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

The solution will be explained below.

@FunctionalInterface
public interface PowerOfTwoFI {
    boolean isPowerOfTwo(int number);
}
public class Solution {
  public static void main(String[] args) {
    PowerOfTwoFI helper = n -> n != 0 && (n & (n - 1)) == 0; // lambda expression

    System.out.println(helper.isPowerOfTwo(4));
    System.out.println(helper.isPowerOfTwo(3));
    System.out.println(helper.isPowerOfTwo(10));
    System.out.println(helper.isPowerOfTwo(16));
  }
}

If you are interested to learn more about Bit Manipulation tricks, I have got a course here on this website which is Grokking Bit Manipulation For Coding Interviews.

Bonus

Benefits of learning Bit Manipulation Tricks

  1. These bit tricks could help in competitive programming is running algorithms mostly in O(1) time.
  2. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies.
  3. By the time you’ve completed this course, you will be able to solve problems faster with greater efficiency on platforms like LeetCode, HackerRank, HackerEarth, CodeForces, CodeChef, SPOJ, etc.
Coding Interview QuestionsJavaJava Streams API

Gopi Gorantala Twitter

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.

Comments


Related Posts

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

Leetcode 217: Contains Duplicate
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,

Leetcode 121: Best Time To Buy and Sell Stock
Members Public

Differences Between JDK, JRE, and JVM?

Short answer JDK, JRE, and JVM are essential components of the Java platform, each serving a distinct purpose. Here are the key differences between them: 1. JDK (Java Development Kit): The JDK is used by developers to write, compile, and debug Java code. 2. JRE (Java Runtime Environment): End-users use