Print numbers having first and last bits as the only set bits

0 0 8 minutes read

Given a positive integer n. The problem is to print numbers in the range 1 to n having first and last bits as the only set bits.
Examples:

Input : n = 10
Output : 1 3 5 9
(1)₁₀ = (1)₂.
(3)₁₀ = (11)₂.
(5)₁₀ = (101)₂.
(9)₁₀ = (1001)₂

Naive Approach: Print “1”. Now for i = 3 to n, check if (i-1) is a Perfect power of two or not. If true then print i.

C++

// C++ implementation to print numbers in the range 1 to n 
// having first and last bits as the only set bits 
#include <bits/stdc++.h> 
  
using namespace std; 
  
typedef unsigned long long int ull; 
  
// function to check whether 'n' 
// is a power of 2 or not 
bool powerOfTwo(ull n) 
{ 
    return (!(n & n-1)); 
} 
  
// function to print numbers in the range 1 to n having 
// first and last bits as the only set bits 
void printNumWithFirstLastBitsSet(ull n) 
{ 
    ull i = 1; 
      
    // first number is '1'     
    cout << i << " "; 
      
    // generating all the numbers 
    for (i = 3; i <= n; i++) 
        // if true, then print 'i' 
        if (powerOfTwo(i-1)) 
            cout << i << " ";     
} 
  
// Driver program to test above 
int main() 
{ 
    ull n = 10; 
    printNumWithFirstLastBitsSet(n); 
    return 0; 
}  

Java

// Naive approach  
// Java implementation to print 
// numbers in the range 1 to n 
// having first and last bits as 
// the only set bits 
import java.io.*; 
  
class GFG { 
      
    // function to check whether 'n' 
    // is a power of 2 or not 
    static Boolean powerOfTwo(long n) 
    { 
        return (!((n & n-1) != 0)); 
    } 
      
    // function to print numbers in the  
    // range 1 to n having first and 
    // last bits as the only set bits 
    static void printNumWithFirstLastBitsSet(long n) 
    { 
        long i = 1; 
          
        // first number is '1'  
        System.out.print( i + " "); 
          
        // generating all the numbers 
        for (i = 3; i <= n; i++) 
          
            // if true, then print 'i' 
            if (powerOfTwo(i - 1)) 
                System.out.print(i + " ");  
    } 
        // Driver function 
        public static void main (String[] args) { 
        long n = 10l; 
        printNumWithFirstLastBitsSet(n); 
      
        } 
} 
  
//This code is contributed by Gitanjali. 

Python3

# Python implementation to print  
# numbers in the range 1 to n 
# having first and last bits  
# as the only set bits 
import math 
  
# function to check whether 'n' 
# is a power of 2 or not 
def powerOfTwo(n): 
    re = (n & n - 1) 
    return (re == 0) 
  
# function to print numbers  
# in the range 1 to n having 
# first and last bits as  
# the only set bits 
def printNumWithFirstLastBitsSet(n): 
    i = 1
      
    # first number is '1'  
    print ( i, end = " ") 
      
    # generating all the numbers 
    for i in range(3, n + 1): 
          
        # if true, then print 'i' 
        if (powerOfTwo(i - 1)): 
            print ( i, end = " ") 
      
      
# driver function 
n = 10
printNumWithFirstLastBitsSet(n) 
  
# This code is contributed by Gitanjali. 

C#

// Naive approach  
// C# implementation to print 
// numbers in the range 1 to n 
// having first and last bits as 
// the only set bits 
using System; 
  
class GFG { 
      
    // function to check whether 'n' 
    // is a power of 2 or not 
    static Boolean powerOfTwo(long n) 
    { 
        return (!((n & n-1) != 0)); 
    } 
      
    // function to print numbers in the  
    // range 1 to n having first and 
    // last bits as the only set bits 
    static void printNumWithFirstLastBitsSet(long n) 
    { 
        long i = 1; 
          
        // first number is '1'  
        Console.Write( i + " "); 
          
        // generating all the numbers 
        for (i = 3; i <= n; i++) 
          
            // if true, then print 'i' 
            if (powerOfTwo(i - 1)) 
                Console.Write(i + " ");  
    } 
      
    // Driver function 
    public static void Main ()  
    { 
        long n = 10L; 
        printNumWithFirstLastBitsSet(n); 
          
    } 
} 
  
// This code is contributed by Vt_m. 

PHP

<?php 
// php implementation to print  
// numbers in the range 1 to n 
// having first and last bits  
// as the only set bits 
  
// function to check whether 'n' 
// is a power of 2 or not 
function powerOfTwo($n) 
{ 
    return (!($n & $n - 1)); 
} 
  
// function to print numbers in 
// the range 1 to n having 
// first and last bits as 
// the only set bits 
function printNumWithFirstLastBitsSet($n) 
{ 
    $i = 1; 
      
    // first number is '1'  
    echo $i." "; 
      
    // generating all the numbers 
    for ($i = 3; $i <= $n; $i++) 
      
        // if true, then print 'i' 
        if (powerOfTwo($i - 1)) 
            echo $i." ";  
} 
  
    // Driver Code 
    $n = 10; 
    printNumWithFirstLastBitsSet($n); 
  
// This Code is contributed by mits  
?> 

Javascript

<script> 
  
// Javascript implementation to print numbers in the range 1 to n 
// having first and last bits as the only set bits 
  
// function to check whether 'n' 
// is a power of 2 or not 
function powerOfTwo(n) 
{ 
    return (!(n & n-1)); 
} 
  
// function to print numbers in the range 1 to n having 
// first and last bits as the only set bits 
function printNumWithFirstLastBitsSet(n) 
{ 
    let i = 1; 
      
    // first number is '1' 
    document.write(i + " "); 
      
    // generating all the numbers 
    for (i = 3; i <= n; i++) 
        // if true, then print 'i' 
        if (powerOfTwo(i-1)) 
            document.write(i + " "); 
} 
  
// Driver program to test above 
  
    let n = 10; 
    printNumWithFirstLastBitsSet(n); 
  
  
//This code is contributed by Mayank Tyagi 
</script> 

Output:

1 3 5 9

Time Complexity : O(n)

Auxiliary Space: O(1)

Efficient Approach: Print “1”. Now one by one generate perfect power of two (except ‘1’) with the help of bitwise left shift operation. Bitwise xor these numbers with 1 and if result is in the range print them else stop.

C++

// C++ implementation to print numbers in the range 1 to n 
// having first and last bits as the only set bits 
#include <bits/stdc++.h> 
  
using namespace std; 
  
typedef unsigned long long int ull; 
  
// function to print numbers in the range 1 to n having 
// first and last bits as the only set bits 
void printNumWithFirstLastBitsSet(ull n) 
{ 
    ull power_2 = 1, num; 
      
    // first number is '1'     
    cout << power_2 << " "; 
      
    while (1)     
    { 
        // obtaining next perfect power of 2 
        power_2 <<= 1; 
          
        // toggling the last bit to convert  
        // it to as set bit 
        num = power_2 ^ 1; 
          
        // if out of range then break; 
        if (n < num) 
            break; 
              
        // display     
        cout << num << " ";     
    }         
} 
  
// Driver program to test above 
int main() 
{ 
    ull n = 10; 
    printNumWithFirstLastBitsSet(n); 
    return 0; 
} 

Java

// efficient approach Java implementation 
// to print numbers in the range 1 to n 
// having first and last bits as the only set bits 
  
import java.io.*; 
  
class GFG { 
  
    // function to print numbers in  
    // the range 1 to n having first and  
    // last bits as the only set bits 
    static void prNumWithFirstLastBitsSet(long n) 
    { 
        long power_2 = 1, num; 
      
        // first number is '1'  
        System.out.print(power_2 + " "); 
      
        while (true)  
        { 
            // obtaining next perfect power of 2 
            power_2 <<= 1; 
              
            // toggling the last bit to   
            // convert it to as set bit 
            num = power_2 ^ 1; 
              
            // if out of range then break; 
            if (n < num) 
                break; 
                  
            // display  
            System.out.print(num + " ");  
        } 
      
} 
  
    public static void main (String[] args) { 
    long n = 10; 
    prNumWithFirstLastBitsSet(n); 
  
    } 
} 
// This code is contributed by Gitanjali. 

Python3

# Python3 implementation to  
# pr numbers in the range  
# 1 to n having first and  
# last bits as the only set bits 
  
  
# function to print numbers in the  
# range 1 to n having first and  
# last bits as the only set bits 
def prNumWithFirstLastBitsSet(n): 
      
    power_2 = 1
      
    # first number is '1'  
    print ( power_2, end = ' ') 
      
    while (1): 
        # obtaining next perfect 
        # power of 2 
        power_2 <<= 1
          
        # toggling the last bit to   
        # convert it to as set bit 
        num = power_2 ^ 1
          
        # if out of range then break; 
        if (n < num): 
            break
              
        # display  
        print ( num, end = ' ')  
      
  
  
# Driver program  
n = 10; 
prNumWithFirstLastBitsSet(n) 
  
# This code is contributed by saloni1297 

C#

// efficient approach C# implementation 
// to print numbers in the range 1 to n 
// having first and last bits as the only set bits 
using System; 
  
class GFG { 
  
    // function to print numbers in  
    // the range 1 to n having first and  
    // last bits as the only set bits 
    static void prNumWithFirstLastBitsSet(long n) 
    { 
        long power_2 = 1, num; 
      
        // first number is '1'  
        Console.Write(power_2 + " "); 
      
        while (true)  
        { 
            // obtaining next perfect power of 2 
            power_2 <<= 1; 
              
            // toggling the last bit to  
            // convert it to as set bit 
            num = power_2 ^ 1; 
              
            // if out of range then break; 
            if (n < num) 
                break; 
                  
            // display  
            Console.Write(num + " ");  
        } 
      
    } 
      
    // Driver code 
    public static void Main ()  
    { 
        long n = 10; 
        prNumWithFirstLastBitsSet(n); 
  
    } 
} 
// This code is contributed by vt_m. 

PHP

<?php 
// php implementation to print  
// numbers in the range 1 to n 
// having first and last bits  
// as the only set bits 
  
// function to print numbers in  
// the range 1 to n having 
// first and last bits as  
// the only set bits 
function printNumWithFirstLastBitsSet($n) 
{ 
    $power_2 = 1; 
      
    // first number is '1'  
    echo $power_2." "; 
      
    while (1)  
    { 
          
        // obtaining next perfect 
        // power of 2 
        $power_2 <<= 1; 
          
        // toggling the last 
        // bit to convert  
        // it to as set bit 
        $num = $power_2 ^ 1; 
          
        // if out of range  
        // then break; 
        if ($n < $num) 
            break; 
              
        // display  
        echo $num." ";  
    }  
} 
  
    // Driver code 
    $n = 10; 
    printNumWithFirstLastBitsSet($n); 
  
// This code is contributed by mits  
?> 

Javascript

<script> 
  
// Javascript implementation to print numbers in the range 1 to n  
// having first and last bits as the only set bits  
  
// function to print numbers in the range 1 to n having  
// first and last bits as the only set bits  
function printNumWithFirstLastBitsSet(n)  
{  
    var power_2 = 1, num;  
      
    // first number is '1'      
    document.write(power_2 + " ");  
      
    while (true)      
    {  
        // obtaining next perfect power of 2  
        power_2 <<= 1;  
          
        // toggling the last bit to convert  
        // it to as set bit  
        num = power_2 ^ 1;  
          
        // if out of range then break;  
        if (n < num)  
            break;  
              
        // display      
        document.write(num + " ");      
    }          
}  
  
// Driver program to test above  
var n = 10;  
printNumWithFirstLastBitsSet(n);  
      
</script>

Output:

1 3 5 9

Time Complexity : O(logn)

Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!