Given a positive integer n, check whether only the first and last bits are set in the binary representation of n. Print ‘Yes’ or ‘No’.
Examples:
Input: 9
Output: Yes
(9)10 = (1001)2, only the first and
last bits are set.Input: 15
Output: No
(15)10 = (1111)2, except first and last
there are other bits also which are set.
We have already discussed a solution here.
In this post, a simpler solution is discussed.
Any number with first and last bits set are of the form (1+2^n):
2^n => 10000… (n zeroes)
+ 1 + 1
————————————-
(1 + 2^n) => 10000….1 (n-1 zeroes)
For any given number ‘N’ of the form (1 + 2^n), we have: ((N-1) & (N-2)) = 0
((1 + 2^n) – 1) => (2^n) => 10000…. (n zeroes)
& ((1 + 2^n) – 2) => &((2^n) – 1) => 01111…. (n 1’s)
————————————————————–
00000….
For example: ‘9’ is of the form (1 + 2^3)
(9)10 => (1001)2
(8)10 => (1000)2
&(7)10 =>& (0111)2
———————–
(0000)2
Hence for any given number ‘N’, if ((N-1) & (N-2)) == 0, then we can say ‘N’ has only first and last bits set.
C++
// C++ to check whether the number has only// first and last bits set#include <bits/stdc++.h>using namespace std;// function to check whether the number has only// first and last bits setbool onlyFirstAndLastAreSet(unsigned int n){ if (n == 1) return true; if (n == 2) return false; return (((n - 1) & (n - 2)) == 0);}// Driver program to test aboveint main(){ unsigned int n = 9; if (onlyFirstAndLastAreSet(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java to check whether // the number has only// first and last bits setclass GFG{// function to check whether// the number has only// first and last bits setstatic boolean onlyFirstAndLastAreSet(int n){ if (n == 1) return true; if (n == 2) return false; return (((n - 1) & (n - 2)) == 0);}// Driver Codepublic static void main(String[] args){ int n = 9; if (onlyFirstAndLastAreSet(n)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed// by Smitha |
Python3
# Python 3 to check whether# the number has only# first and last bits set# function to check whether# the number has only# first and last bits setdef onlyFirstAndLastAreSet(n): if (n == 1): return True if (n == 2): return False return (((n - 1) & (n - 2)) == 0)# Driver Coden = 9if (onlyFirstAndLastAreSet(n)): print("Yes")else: print("No") # This code is contributed# by Smitha |
C#
// C# to check whether // the number has only// first and last bits setusing System;class GFG{// function to check whether// the number has only// first and last bits setstatic bool onlyFirstAndLastAreSet(int n){ if (n == 1) return true; if (n == 2) return false; return (((n - 1) & (n - 2)) == 0);}// Driver Codepublic static void Main(){ int n = 9; if (onlyFirstAndLastAreSet(n)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed // by Smitha |
PHP
<?php// PHP to check whether the // number has only first and // last bits set// function to check whether // the number has only first // and last bits setfunction onlyFirstAndLastAreSet($n){ if ($n == 1) return true; if ($n == 2) return false; return ((($n - 1) & ($n - 2)) == 0);}// Driver Code$n = 9;if (onlyFirstAndLastAreSet($n)) echo "Yes";else echo "No"; // This code is contributed// by Smitha?> |
Javascript
<script>// javascript to check whether // the number has only// first and last bits set// function to check whether// the number has only// first and last bits setfunction onlyFirstAndLastAreSet(n){ if (n == 1) return true; if (n == 2) return false; return (((n - 1) & (n - 2)) == 0);}// Driver Codevar n = 9;if (onlyFirstAndLastAreSet(n)) document.write("Yes");else document.write("No");// This code contributed by shikhasingrajput </script> |
Yes
Time complexity: O(1)
Auxiliary space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!