Given a positive integer n. The problem is to print the numbers in the range 1 to n having bits in alternate pattern. Here alternate pattern means that the set and unset bits in the number occur in alternate order. For example- 5 has an alternate pattern i.e. 101.
Examples:
Input : n = 10 Output : 1 2 5 10 Input : n = 50 Output : 1 2 5 10 21 42
Method 1 (Naive Approach): Generate all the numbers in the range 1 to n and for each generated number check whether it has bits in alternate pattern. Time Complexity is of O(n).
Method 2 (Efficient Approach): Algorithm:
printNumHavingAltBitPatrn(n)
Initialize curr_num = 1
print curr_num
while (1)
curr_num <<= 1
if n < curr_num then
break
print curr_num
curr_num = ((curr_num) << 1) ^ 1
if n < curr_num then
break
print curr_num
CPP
// C++ implementation to print numbers in the range// 1 to n having bits in alternate pattern#include <bits/stdc++.h>using namespace std;// function to print numbers in the range 1 to n// having bits in alternate patternvoid printNumHavingAltBitPatrn(int n){ // first number having bits in alternate pattern int curr_num = 1; // display cout << curr_num << " "; // loop until n < curr_num while (1) { // generate next number having alternate // bit pattern curr_num <<= 1; // if true then break if (n < curr_num) break; // display cout << curr_num << " "; // generate next number having alternate // bit pattern curr_num = ((curr_num) << 1) ^ 1; // if true then break if (n < curr_num) break; // display cout << curr_num << " "; }}// Driver program to test aboveint main(){ int n = 50; printNumHavingAltBitPatrn(n); return 0;} |
Java
// Java implementation to print numbers in the range// 1 to n having bits in alternate patternimport java.io.*;import java.util.*;class GFG{ public static void printNumHavingAltBitPatrn(int n) { // first number having bits in alternate pattern int curr_num = 1, i = 1; // display System.out.print(curr_num + " "); // loop until n < curr_num while (i!=0) { i++; // generate next number having alternate // bit pattern curr_num <<= 1; // if true then break if (n < curr_num) break; // display System.out.print(curr_num + " "); // generate next number having alternate // bit pattern curr_num = ((curr_num) << 1) ^ 1; // if true then break if (n < curr_num) break; // display System.out.print(curr_num + " "); } } public static void main (String[] args) { int n = 50; printNumHavingAltBitPatrn(n); }}// Code Contributed by Mohit Gupta_OMG <(0_o)> |
Python3
# Python3 program for count total# zero in product of array# function to print numbers in the range # 1 to nhaving bits in alternate patterndef printNumHavingAltBitPatrn(n): # first number having bits in # alternate pattern curr_num = 1 # display print (curr_num) # loop until n < curr_num while (1) : # generate next number having # alternate bit pattern curr_num = curr_num << 1; # if true then break if (n < curr_num): break; # display print( curr_num ) # generate next number having # alternate bit pattern curr_num = ((curr_num) << 1) ^ 1; # if true then break if (n < curr_num): break # display print( curr_num )# Driven coden = 50printNumHavingAltBitPatrn(n) # This code is contributed by "rishabh_jain". |
C#
// C# implementation to print numbers in the range// 1 to n having bits in alternate patternusing System;class GFG { // function to print numbers in the range 1 to n // having bits in alternate pattern public static void printNumHavingAltBitPatrn(int n) { // first number having bits in alternate pattern int curr_num = 1, i = 1; // display Console.Write(curr_num + " "); // loop until n < curr_num while (i!=0) { // generate next number having alternate // bit pattern curr_num <<= 1; // if true then break if (n < curr_num) break; // display Console.Write(curr_num + " "); // generate next number having alternate // bit pattern curr_num = ((curr_num) << 1) ^ 1; // if true then break if (n < curr_num) break; // display Console.Write(curr_num + " "); } } // Driver code public static void Main () { int n = 50; printNumHavingAltBitPatrn(n); }}// This code is contributed by Sam007. |
PHP
<?php// php implementation to print // numbers in the range// 1 to n having bits in // alternate pattern// function to print numbers// in the range 1 to n// having bits in alternate // patternfunction printNumHavingAltBitPatrn($n){ // first number having bits // in alternate pattern $curr_num = 1; // display echo $curr_num." "; // loop until n < curr_num while (1) { // generate next number // having alternate // bit pattern $curr_num <<= 1; // if true then break if ($n < $curr_num) break; // display echo $curr_num." "; // generate next number // having alternate // bit pattern $curr_num = (($curr_num) << 1) ^ 1; // if true then break if ($n < $curr_num) break; // display echo $curr_num." "; }} // Driver code $n = 50; printNumHavingAltBitPatrn($n);// This code is contributed by mits ?> |
Javascript
<script>// Javascript implementation to print numbers in the range // 1 to n having bits in alternate pattern // function to print numbers in the range 1 to n // having bits in alternate pattern function printNumHavingAltBitPatrn(n) { // first number having bits in alternate pattern var curr_num = 1; // display document.write(curr_num + " "); // loop until n < curr_num while (true) { // generate next number having alternate // bit pattern curr_num <<= 1; // if true then break if (n < curr_num) break; // display document.write(curr_num + " "); // generate next number having alternate // bit pattern curr_num = ((curr_num) << 1) ^ 1; // if true then break if (n < curr_num) break; // display document.write(curr_num + " "); } } // Driver program to test above var n = 50; printNumHavingAltBitPatrn(n); </script> |
Output:
1 2 5 10 21 42
Time Complexity: O(log n)
Space Complexity: 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!
