How to get numbers having first and last bits as the only set bit

Problem overview

Given a number n, find the numbers from 1 to n that have the first and last bit set.

Example 1:

  • Input: n=7
  • Output: 1 2 3 5

Example 2:

  • Input: n=35
  • Output: 1 2 3 5 9 17 33

Solution

The simplest and most straightforward way to solve this problem is for every number from 1 to n to check if the first and last bits are set.

The algorithm described in Check if first and last bit of a number are the only set bits can be used to check if the first and last bit of a number of are only set bits.

  • The time complexity is O(n)O(n).
  • The space complexity is O(1)O(1).

Code example

Let’s look at the code below:

import java.util.ArrayList;
import java.util.List;
public class Main{
    static boolean isPowerOfTwo(int n) {
        return ((n & n - 1) == 0);
    }
    static boolean isOnlyFirstAndLastBitsAreSet(int n) {
        return (n == 1) || isPowerOfTwo(n - 1);
    }
    static List<Integer> numsLastAndFirstBitSet(int n){
        List<Integer> integerList = new ArrayList<>();
        for(int i = 1; i<=n;i++) if(isOnlyFirstAndLastBitsAreSet(i)) integerList.add(i);
        return integerList;
    }
    public static void main(String[] arg) {
        int n = 35;
        System.out.println("The numbers that have first and last bit set are as follows:" + numsLastAndFirstBitSet(n));
    }
}

Code explanation

  • Lines 6–12: Refer to Check if first and last bit of a number are the only set bits.
  • Lines 14–18: The numsLastAndFirstBitSet() method is defined where every number from 1 to n is checked for first and last bit sets with the help of isOnlyFirstAndLastBitsAreSet() method.
  • Line 21: The n is defined.
  • Line 22: The numsLastAndFirstBitSet() method is invoked with n as the argument.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved