Given a positive integer N, the task is to find a number which contains (N – 1) set bits in its binary form at every even index (1-based) from the right.
Examples:
Input: N = 2
Output: 2
Binary representation of 2 is 10 which has
1 set bit at even position from the right.
Input: N = 4
Output: 42
Binary representation of 42 is 101010
Observation: If we check out the numbers in binary form then the result is something like this:
n | Decimal Equivalent | Binary Equivalent |
---|---|---|
1 | 0 | 0 |
2 | 2 | 10 |
3 | 10 | 1010 |
4 | 42 | 101010 |
5 | 170 | 10101010 |
Naive Approach: As we can see in the table our binary equivalent is always adding a “10” in last of the previous string. So, we can generate a binary string which is made up of sub-string “10” concatenated N-1 times and then print its decimal equivalent.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define ll long long int // Function to return the string generated // by appending "10" n-1 times string constructString(ll n) { // Initialising string as empty string s = "" ; for (ll i = 0; i < n; i++) { s += "10" ; } return s; } // Function to return the decimal equivalent // of the given binary string ll binaryToDecimal(string n) { string num = n; ll dec_value = 0; // Initializing base value to 1 // i.e 2^0 ll base = 1; ll len = num.length(); for (ll i = len - 1; i >= 0; i--) { if (num[i] == '1' ) dec_value += base; base = base * 2; } return dec_value; } // Function that calls the constructString // and binarytodecimal and returns the answer ll findNumber(ll n) { string s = constructString(n - 1); ll num = binaryToDecimal(s); return num; } // Driver code int main() { ll n = 4; cout << findNumber(n); return 0; } |
Java
// Java implementation of above approach import java.util.*; class GFG { // Function to return the String generated // by appending "10" n-1 times static String constructString( int n) { // Initialising String as empty String s = "" ; for ( int i = 0 ; i < n; i++) { s += "10" ; } return s; } // Function to return the decimal equivalent // of the given binary String static int binaryToDecimal(String n) { String num = n; int dec_value = 0 ; // Initializing base value to 1 // i.e 2^0 int base = 1 ; int len = num.length(); for ( int i = len - 1 ; i >= 0 ; i--) { if (num.charAt(i) == '1' ) dec_value += base; base = base * 2 ; } return dec_value; } // Function that calls the constructString // and binarytodecimal and returns the answer static int findNumber( int n) { String s = constructString(n - 1 ); int num = binaryToDecimal(s); return num; } // Driver code public static void main(String[] args) { int n = 4 ; System.out.println(findNumber(n)); } } /* This code is contributed by PrinciRaj1992 */ |
Python
# Python3 implementation of the approach # Function to return the generated # by appending "10" n-1 times def constructString(n): # Initialising as empty s = "" for i in range (n): s + = "10" return s # Function to return the decimal equivaLent # of the given binary string def binaryToDecimal(n): num = n dec_value = 0 # Initializing base value to 1 # i.e 2^0 base = 1 Len = len (num) for i in range ( Len - 1 , - 1 , - 1 ): if (num[i] = = '1' ): dec_value + = base base = base * 2 return dec_value # Function that calls the constructString # and binarytodecimal and returns the answer def findNumber(n): s = constructString(n - 1 ) num = binaryToDecimal(s) return num # Driver code n = 4 print (findNumber(n)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of above approach using System; class GFG { // Function to return the String generated // by appending "10" n-1 times static String constructString( int n) { // Initialising String as empty String s = "" ; for ( int i = 0; i < n; i++) { s += "10" ; } return s; } // Function to return the decimal equivalent // of the given binary String static int binaryToDecimal(String n) { String num = n; int dec_value = 0; // Initializing base value to 1 // i.e 2^0 int base_t = 1; int len = num.Length; for ( int i = len - 1; i >= 0; i--) { if (num[i] == '1' ) dec_value = dec_value + base_t; base_t = base_t * 2; } return dec_value; } // Function that calls the constructString // and binarytodecimal and returns the answer static int findNumber( int n) { String s = constructString(n - 1); int num = binaryToDecimal(s); return num; } // Driver code static public void Main () { int n = 4; Console.Write(findNumber(n)); } } // This code is contributed by ajit |
Javascript
<script> // JavaScript implementation of above approach // Function to return the String generated // by appending "10" n-1 times function constructString(n) { // Initialising String as empty var s = "" ; for ( var i = 0; i < n; i++) { s += "10" ; } return s; } // Function to return the decimal equivalent // of the given binary String function binaryToDecimal(n) { var num = n; var dec_value = 0; // Initializing base value to 1 // i.e 2^0 var base = 1; var len = num.length; for ( var i = len - 1; i >= 0; i--) { if (num.charAt(i) == '1' ) dec_value += base; base = base * 2; } return dec_value; } // Function that calls the constructString // and binarytodecimal and returns the answer function findNumber(n) { var s = constructString(n - 1); var num = binaryToDecimal(s); return num; } // Driver code var n = 4; document.write(findNumber(n)); // This code is contributed by Amit Katiyar </script> |
42
Efficient Approach: If we take the numbers and convert them to base 4 we can see an interesting pattern as follows:
n | Decimal Equivalent | Binary Equivalent | Base_4 |
---|---|---|---|
1 | 0 | 0 | 0 |
2 | 2 | 10 | 2 |
3 | 10 | 1010 | 22 |
4 | 42 | 101010 | 222 |
5 | 170 | 10101010 | 2222 |
We are actually appending “2” for every nth term in base4 i.e. for n = 7 our number in base4 would have (n – 1) i.e. 6 consecutive 2’s.
Now we have to take a point in mind as we know that if we convert from any base m to base 10 i.e. decimal than the solution is (n0 * m0 + n1 * m1 + n2 * m2 + …. + n * mn). So as our base is 4 by further calculation we can found that our required number n can be found by using the deduced formula in O(1) time complexity.
Formula:
A(n) = floor((2 / 3) * (4n – 1))
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define ll long long int // Function to compute number // using our deduced formula ll findNumber( int n) { // Initialize num to n-1 ll num = n - 1; num = 2 * (ll) pow (4, num); num = floor (num / 3.0); return num; } // Driver code int main() { int n = 5; cout << findNumber(n); return 0; } |
Java
// Java implementation of the approach import java.io.*; class GFG { // Function to compute number // using our deduced formula static int findNumber( int n) { // Initialize num to n-1 int num = n - 1 ; num = 2 * ( int )Math.pow( 4 , num); num = ( int )Math.floor(num / 3.0 ); return num; } // Driver code public static void main (String[] args) { int n = 5 ; System.out.println (findNumber(n)); } } // The code is contributed by ajit. |
Python3
# Python3 implementation of the approach # Function to compute number # using our deduced formula def findNumber(n) : # Initialize num to n-1 num = n - 1 ; num = 2 * ( 4 * * num); num = num / / 3 ; return num; # Driver code if __name__ = = "__main__" : n = 5 ; print (findNumber(n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to compute number // using our deduced formula static int findNumber( int n) { // Initialize num to n-1 int num = n - 1; num = 2 * ( int )Math.Pow(4, num); num = ( int )Math.Floor(num / 3.0); return num; } // Driver code static public void Main () { int n = 5; Console.Write(findNumber(n)); } } // The code is contributed by Tushil. |
Javascript
<script> // Javascript implementation of the approach // Function to compute number // using our deduced formula function findNumber(n) { // Initialize num to n-1 let num = n - 1; num = 2 * Math.pow(4, num); num = Math.floor(num / 3.0); return num; } let n = 5; document.write(findNumber(n)); </script> |
170
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!