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)10 = (1)2. (3)10 = (11)2. (5)10 = (101)2. (9)10 = (1001)2
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 = 10printNumWithFirstLastBitsSet(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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
