Given a number N. The task is to write a program to find the N-th term in the series:
1, 11, 55, 239, 991, …
Examples:
Input: N = 3 Output: 55 Input: N = 4 Output: 239
Approach-1:
On writing down the binary representation of the given numbers, a pattern can be observed.
1 = 1
11 = 1011
55 = 110111
239 = 11101111
.
.
.
Hence for N = 1, the answer will always be one. For N-th term the binary string will be (n-1)*1 + (0) + (n)*1 which is converted to decimal value to get the answer.
Below is the implementation of the above approach:
C++
// C++ program to find the N-th term// in 1, 11, 55, 239, 991, ....#include <bits/stdc++.h>using namespace std;// Function to return the decimal value// of a binary numberint 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[i] == '1') dec_value += base; base = base * 2; } return dec_value;}// find the binary representation// of the N-th number in sequenceint numberSequence(int n){ // base case if (n == 1) return 1; // answer string string s = ""; // add n-1 1's for (int i = 1; i < n; i++) s += '1'; // add 0 s += '0'; // add n 1's at end for (int i = 1; i <= n; i++) s += '1'; int num = binaryToDecimal(s); return num;}// Driver Codeint main(){ int n = 4; cout << numberSequence(n); return 0;} |
Java
// Java program to find the N-th // term in 1, 11, 55, 239, 991, ....import java.util.*;class GFG{// Function to return the decimal// value of a binary numberstatic 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;}// find the binary representation// of the N-th number in sequencestatic int numberSequence(int n){ // base case if (n == 1) return 1; // answer string String s = ""; // add n-1 1's for (int i = 1; i < n; i++) s += '1'; // add 0 s += '0'; // add n 1's at end for (int i = 1; i <= n; i++) s += '1'; int num = binaryToDecimal(s); return num;}// Driver Codepublic static void main(String args[]){ int n = 4; System.out.println(numberSequence(n));}}// This code is contributed // by Arnab Kundu |
Python 3
# Python 3 program to find the N-th term# in 1, 11, 55, 239, 991, .... # Function to return the decimal value# of a binary numberdef binaryToDecimal(n): num = n dec_value = 0 # Initializing base value to 1, i.e 2^0 base = 1 l = len(num) for i in range(l - 1,-1, -1): if (num[i] == '1'): dec_value += base base = base * 2 return dec_value # find the binary representation# of the N-th number in sequencedef numberSequence(n): # base case if (n == 1): return 1 # answer string s = "" # add n-1 1's for i in range(1, n): s += '1' # add 0 s += '0' # add n 1's at end for i in range(1,n+1): s += '1' num = binaryToDecimal(s) return num # Driver Codeif __name__ == "__main__": n = 4 print(numberSequence(n))# this code is contributed by ChitraNayal |
C#
// C# program to find the N-th // term in 1, 11, 55, 239, 991, ....using System;class GFG{// Function to return the decimal// value of a binary numberstatic 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[i] == '1') dec_value += base_; base_ = base_ * 2; } return dec_value;}// find the binary representation// of the N-th number in sequencestatic int numberSequence(int n){ // base case if (n == 1) return 1; // answer string String s = ""; // add n-1 1's for (int i = 1; i < n; i++) s += '1'; // add 0 s += '0'; // add n 1's at end for (int i = 1; i <= n; i++) s += '1'; int num = binaryToDecimal(s); return num;}// Driver Codepublic static void Main(){ int n = 4; Console.WriteLine(numberSequence(n));}}// This code is contributed// by Subhadeep |
PHP
<?php// PHP program to find the N-th term// in 1, 11, 55, 239, 991, ....// Function to return the decimal // value of a binary numberfunction binaryToDecimal($n){ $num = $n; $dec_value = 0; // Initializing base value // to 1, i.e 2^0 $base = 1; $len = strlen($num); for ($i = $len - 1; $i >= 0; $i--) { if ($num[$i] == '1') $dec_value += $base; $base = $base * 2; } return $dec_value;}// find the binary representation// of the N-th number in sequencefunction numberSequence($n){ // base case if ($n == 1) return 1; // answer string $s = ""; // add n-1 1's for ($i = 1; $i < $n; $i++) $s .= '1'; // add 0 $s .= '0'; // add n 1's at end for ($i = 1; $i <= $n; $i++) $s .= '1'; $num = binaryToDecimal($s); return $num;}// Driver Code$n = 4;echo numberSequence($n);// This code is contributed by mits?> |
Javascript
<script>// Javascript program to find the N-th term// in 1, 11, 55, 239, 991, ....// Function to return the decimal value// of a binary numberfunction binaryToDecimal(n){ let num = n; let dec_value = 0; // Initializing base value to 1, i.e 2^0 let base = 1; let len = num.length; for (let i = len - 1; i >= 0; i--) { if (num[i] == '1') dec_value += base; base = base * 2; } return dec_value;}// find the binary representation// of the N-th number in sequencefunction numberSequence(n){ // base case if (n == 1) return 1; // answer string let s = ""; // add n-1 1's for (let i = 1; i < n; i++) s += '1'; // add 0 s += '0'; // add n 1's at end for (let i = 1; i <= n; i++) s += '1'; let num = binaryToDecimal(s); return num;}// Driver Codelet n = 4;document.write(numberSequence(n));// This code is contributed by subhammahato348.</script> |
Output
239
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for string.
Approach-2:
The series has a general formulae of 4N-2N-1 which is used to get the N-th term in series.
Below is the implementation of the above approach:
C++
// C++ program to find the N-th term// in 1, 11, 55, 239, 991, ....#include <bits/stdc++.h>using namespace std;// Function to find the N-th termint numberSequence(int n){ // calculates the N-th term int num = pow(4, n) - pow(2, n) - 1; return num;}// Driver Codeint main(){ int n = 4; cout << numberSequence(n); return 0;} |
Java
// Java program to find the N-th // term in 1, 11, 55, 239, 991, ....class GFG{// Function to find the N-th termstatic int numberSequence(int n){ // calculates the N-th term int num = (int)(Math.pow(4, n) - Math.pow(2, n)) - 1; return num;}// Driver Codepublic static void main(String args[]){ int n = 4; System.out.println(numberSequence(n));}}// This code is contributed // by Arnab Kundu |
Python 3
# Python 3 program to find N-th term # in 1, 11, 55, 239, 991, .... # calculate Nth term of seriesdef numberSequence(n) : # calculates the N-th term num = pow(4, n) - pow(2, n) - 1 return num# Driver Codeif __name__ == "__main__" : n = 4 print(numberSequence(n))# This code is contributed by ANKITRAI1 |
C#
// C# program to find the N-th // term in 1, 11, 55, 239, 991, ....using System;class GFG{// Function to find the N-th termstatic int numberSequence(int n){ // calculates the N-th term int num = (int)(Math.Pow(4, n) - Math.Pow(2, n)) - 1; return num;}// Driver Codepublic static void Main(){ int n = 4; Console.WriteLine(numberSequence(n));}}// This code is contributed // by chandan_jnu. |
PHP
<?php// PHP program to find the N-th term// in 1, 11, 55, 239, 991, ....// Function to find the N-th termfunction numberSequence($n){ // calculates the N-th term $num = pow(4, $n) - pow(2, $n) - 1; return $num;}// Driver Code$n = 4;echo numberSequence($n);// This code is contributed by mits?> |
Javascript
<script>// Javascript program to find the N-th term// in 1, 11, 55, 239, 991, ....// Function to find the N-th termfunction numberSequence(n){ // calculates the N-th term let num = Math.pow(4, n) - Math.pow(2, n) - 1; return num;}// Driver Codelet n = 4;document.write(numberSequence(n));</script> |
Output
239
Time Complexity: O(logN), as we are using pow function which will cost logN time.
Auxiliary Space: O(1), as we are not using any extra space.
Approach-3:
As we can see the pattern in approach 1, here also we use that pattern to calculate N-th term. But instead of string to store, we use bitwise operator(“<<” and “|”) and built-in pow() function to calculate N-th term of the sequence.
Below is the implementation of the above approach:
C++
// C++ program to find the N-th term// in 1, 11, 55, 239, 991, ....#include <bits/stdc++.h>using namespace std;// Find N-th number in sequenceint numberSequence(int n){ // base case if (n == 1) return 1; // value after 0 int q = pow(2, n) - 1; // value before 0 int p = pow(2, (n - 1)) - 1; // calculate N-th term using shifting and OR operation p = p << (n + 1); p = p | q; return p;}// Driver Codeint main(){ int n = 4; cout << numberSequence(n); return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java program to find the N-th term// in 1, 11, 55, 239, 991, ....import java.math.BigInteger;class GFG { public static void main(String[] args) { int n = 4; System.out.println(numberSequence(n)); } public static int numberSequence(int n) { if (n == 1) { return 1; } int q = (int)Math.pow(2, n) - 1; int p = (int)Math.pow(2, n - 1) - 1; p = p << (n + 1); p = p | q; return p; }}// This code is contributed by Susobhan Akhuli |
Python3
# Python program to find the N-th term# in 1, 11, 55, 239, 991, ....import mathdef numberSequence(n: int) -> int: # base case if n == 1: return 1 # value after 0 q = pow(2, n) - 1 # value before 0 p = pow(2, (n - 1)) - 1 # calculate N-th term using shifting and OR operation p = p << (n + 1) p = p | q return p# Driver Coden = 4print(numberSequence(n))# This code is contributed by Susobhan Akhuli |
C#
// C# program to find the N-th term// in 1, 11, 55, 239, 991, ....using System;class Program { // Find N-th number in sequence static int numberSequence(int n) { // base case if (n == 1) return 1; // value after 0 int q = (int)Math.Pow(2, n) - 1; // value before 0 int p = (int)Math.Pow(2, (n - 1)) - 1; // calculate N-th term using shifting and OR // operation p = p << (n + 1); p = p | q; return p; } // Driver code static void Main(string[] args) { int n = 4; Console.WriteLine(numberSequence(n)); }}// This code is contributed by Susobhan Akhuli |
Javascript
// Find N-th number in sequencefunction numberSequence(n) { // base case if (n === 1) { return 1; } // value after 0 let q = Math.pow(2, n) - 1; // value before 0 let p = Math.pow(2, n - 1) - 1; // calculate N-th term using shifting and OR operation p = p << (n + 1); p = p | q; return p;}// Driver Codelet n = 4;console.log(numberSequence(n)); |
Output
239
Time Complexity: O(logN) [For pow function]
Auxiliary Space: O(1)
Approach-4:
As we can see the pattern in approach 2, here do the same but instead of using pow() function, here we use the math.log2() in combination with the operator “**” to calculate N-th term of the sequence.
Below is the implementation of the above approach:
C++
// CPP program to find N-th term// in 1, 11, 55, 239, 991, ....#include <cmath>#include <iostream>using namespace std;// calculates Nth term of seriesint numberSequence(int n){ // calculates the N-th term int num = pow(2, n * (int)(log2(4))) - pow(2, n * (int)(log2(2))) - 1; return num;}// Driver Codeint main(){ int n = 4; cout << numberSequence(n) << endl; return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java program to find N-th term// in 1, 11, 55, 239, 991, ....import java.lang.Math;public class GFG { // calculates Nth term of series public static int numberSequence(int n) { // calculates the N-th term int num = (int)Math.pow( 2, n * (int)(Math.log(4) / Math.log(2))) - (int)Math.pow( 2, n * (int)(Math.log(2) / Math.log(2))) - 1; return num; } public static void main(String[] args) { int n = 4; System.out.println(numberSequence(n)); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python 3 program to find N-th term# in 1, 11, 55, 239, 991, ....import math# calculate Nth term of seriesdef numberSequence(n): # calculates the N-th term num = 2 ** (n * int(math.log2(4))) - 2 ** (n * int(math.log2(2))) - 1 return num# Driver Codeif __name__ == "__main__": n = 4 print(numberSequence(n))# This code is contributed by Susobhan Akhuli |
C#
// C# program to find N-th term// in 1, 11, 55, 239, 991, ....using System;class GFG { // calculates Nth term of series static int NumberSequence(int n) { // calculates the N-th term int num = (int)(Math.Pow(2, n * (int)(Math.Log(4, 2)))) - (int)(Math.Pow(2, n * (int)(Math.Log(2, 2)))) - 1; return num; } // Driver Code static void Main(string[] args) { int n = 4; Console.WriteLine(NumberSequence(n)); }}// This code is contributed by Susobhan Akhuli |
Javascript
// calculate Nth term of seriesfunction numberSequence(n) {// calculates the N-th termlet num = Math.pow(2, n * Math.log2(4)) - Math.pow(2, n * Math.log2(2)) - 1;return num;}// Driver Codeconst n = 4;console.log(numberSequence(n)); |
Output
239
Time Complexity: O(Log(exponent))
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!
Share your thoughts in the comments
