Binary Strings Without Consecutive Ones in Java

N, an integer, is provided. Our objective is to determine the overall number of strings with length N that do not include successive 1s.

Example:

Input: 3

Output: 6

Explanation

The binary forms of length 3 are:

000 010 001 100 011 100 101 110 111 among these, all the possibilities 000, 010, 001, 100, 100, 101 are only possible forms as they do not contain the consecutive 1’s.

Recursive Method

There will be 2N potential binary sequences for a length N. Using the common method of backtracking, we can perform some trimming and construct just the strings that meet the requirements. We'll use straightforward recurrence. Since we only need to construct binary strings, there are simply two potential bits that can insert in each jth position. A 1 can only be positioned at position j if the position (j - 1) would not already have a 1. Expressed, the number of binary strings produced when 1 is inserted at location j equals the amount produced when 0 is inserted at location (j - 1).

1. Put a value of 0 into the variable "sol". It saves the last digit of binary representation without a run of successive ones.

2. Execute the recursive procedure twice. Give the process parameters in the initial recursive call the 0-bit and leftmost columns the process parameters, then the 1-bit and leftmost columns in the subsequent recursive call.

The initial recurrent call returns the total amount of binary representation with 0 as the final bit. They don't have any consecutive 1s, either.

The first iteration step provides the number of binary strings, with 1a as its final bit. They don't have any successive 1s either.

Step 3: The recursive technique involves:

Define the fundamental criterion for stopping the nested loops: return 1 if the present index "index" decreases to 0.

Do the recursion calls to the preceding index, sending "current" as 0 in one operation and "current" as 1 in the second call if the present bit (that needs to be inserted) is zero.

Should make the only recursion call to the preceding index with the present bit (which has to be put) set to 0, as well as the value delivered from any of these calls should be 1 if the present bit is 1.

Example:BinaryStrings.java

// this program is to find the number of binary strings possible for a given length
//importing the required packages
import java.io.*;
import java.util.*;
public class BinaryStrings   
{  
public int numberOfBinaryStrings(int num)   
{  
// the variable is initialized for the outcome
int s = 0;  
// the recursive functions.  
s= numberOfBinaryStringsUtil(num - 1, 0);  
s = s + numberOfBinaryStringsUtil(num - 1, 1);  
//  the value is returned
return s;  
}  
//  reading the input method
public int numberOfBinaryStringsUtil(int indxs, int currBits)   
{  
// the base condition for the input.  
if (indxs == 0)   
{  
return 1;  
}  
// The preceding bit / may be either 0 or 1 if "currBits" matches 0.  
if (currBits == 0)   
{  
return (numberOfBinaryStringsUtil(indxs - 1, 1) +  
    numberOfBinaryStringsUtil(indxs - 1, 0));  
}  
// If 'currents' is 1,  then the bit in the previous position is 0
else if (currBits == 1)   
{  
return numberOfBinaryStringsUtil(indxs - 1, 0);  
}  
return 0;  
}  
// Main section of the java program  
public static void main(String[] argvs)   
{ 
//  an object ob is created for BinaryStrings class
BinaryStrings ob = new BinaryStrings();  
// the user input 1 
int Num = 4;  
int s = ob.numberOfBinaryStrings(Num);  
System.out.println("The given size of the binary string: " + Num);  
if(s != 0)  
{  
System.out.println("It contains  " + s + " strings which are not contain successive one's.");  
}  
else  
{  
System.out.println("There isn't a binary sequence that contains successive 1.");     
}  
System.out.println("\n");  
// user input 2 
Num= 2;  
s = ob.numberOfBinaryStrings(Num);  
System.out.println("The given size of the binary string: " + Num);  
if(s != 0)  
{  
System.out.println("It contains  " + s + " strings which are not contain successive one's.");  
}  
else  
{  
System.out.println("No binary string exists which contains successive ones.");     
}  
}  
}  

Output

The given size of the binary string: 4
It contains 8 strings which are not contain successive one's.




The given size of the binary string: 2
It contains 3 strings which are not contain successive one’s.

Program running time is O(2n), whereby n is the length of the binary format due to the service's use of actually taking calls. Because no computational models are used in the program, its case complexity is O(1).

The program's temporal complexity is just too high. As a result, the proposed method is impractical for bigger inputs. There needs to be some improvement done as a result. The next method demonstrates the very same.

Using Dynamic Programming

Step 1: Put a value of 0 into the variable "sol." It saves the last digit of binary without a run of successive ones.

Step two constructs a two-dimensional array of size (2 * N) called "dpArr". Give the array dpArr's components all the value "-1." In this case, dpArr[p][q] yields the number of binary with a size equivalent to p and the final bit identical to q. DpArr[0][0] = 1 and DpArr[0][1] = 1 will constitute the basic conditions.

Step 2: Call the procedure that counts the total number of binary representations that do not include successive ones twice using broadcast. Send the last location, the 0-bit, and the door as arguments to the initial iteration step.

The 1-bit, the last location, and the dpArrs are sent as arguments in the subsequent iteration step.

The initial iteration step returns the entire amount of binary strings with 0 as their final bit. Furthermore, there are no successive 1s in them.

The first recursive call returns the overall number of binary with 1a as the final bit. Furthermore, there are no successive 1s in them.

Step 3: When using the recursive method:

• Establish the fundamental criterion for stopping the repetition: return a value matching to the dpArrs if the present index, index, reaches 0.
• A result again for the number indx and the currBits has already been determined if the value of dp[indx][currBit] is indeed not equal to -1. thus provide the result dp[indx][currBit].
• When calling the preceding index recursively, send the current bit (which has to be inserted) "currBits" as 0 inside one function and as 1 in the second if it is zero. Retain the dpArr's total response to all these recurrent calls.
• If the currently required bit, "currBits," is 1, then perhaps the single recursion call to the preceding index should be made, passing "currents" as 0, and the result should be stored in the dpArr.

Example: BinaryStrings1.java

// this program is to find the number of binary strings possible for a given length
//importing the required packages
import java.io.*;
public class BinaryStrings1   
{  
public int numberOfBinaryStrings(int nums)   
{  
// setting the parameter "sols" to zero to maintain the result.  
int sols = 0;  
int[][] dpArrs = new int[nums][2];  
// the array is initialized 
// default value as -1 
for(int j = 0; j < nums; j++)  
{  
dpArrs[j][0] = -1;  
dpArrs[j][1] = -1;  
}  
dpArrs[0][0] = 1;  
dpArrs[0][1] = 1;  
//  the repetive calls
sols = numberOfBinaryStringsUtil(nums - 1, 0, dpArrs);  
sols = sols+numberOfBinaryStringsUtil(nums - 1, 1, dpArrs);  
//the result is at the end
return sols;  
}  
// the method.  
public int numberOfBinaryStringsUtil(int indxs, int currBits, int dpArrs[][])   
{  
//  the base condition is giving 
if (indxs == 0)   
{  
return dpArrs[indxs][currBits];  
}  
// as for the value of the index or current If dpArr[indx][currBit] 
//is greater than 0 and less than 1; its result has been calculated.
//We only need to provide the value.
if (dpArrs[indxs][currBits] != -1)   
{  
return dpArrs[indxs][currBits];  
}  
// The preceding bit  
//may be either 1 or 0 if "current" matches 0.
if (currBits == 0)   
{  
dpArrs[indxs][currBits] = (numberOfBinaryStringsUtil(indxs - 1, 1, dpArrs) +  
    numberOfBinaryStringsUtil(indxs - 1, 0, dpArrs));  
}  
//
else if (currBits == 1)   
{  
dpArrs[indxs][currBits] = numberOfBinaryStringsUtil(indxs - 1, 0, dpArrs);  
}  
return dpArrs[indxs][currBits];  
}  
// Main section of the program 
public static void main(String[] argvs)   
{  
//  an object is created for BinaryStrings1 class
BinaryStrings1 ob = new BinaryStrings1();  
// input 1  
int Num = 4;  
int sols = ob.numberOfBinaryStrings(Num);  
System.out.println("The given size of the binary string: " + Num);  
if(sols != 0)  
{  
System.out.println("It contains  " + sols + " strings which are not contain successive one's.");  
}  
else  
{  
System.out.println("There isn't a binary sequence that contains successive 1.");     
}  
System.out.println("\n");  
// input 2  
Num = 2;  
sols = ob.numberOfBinaryStrings(Num);  
System.out.println("The given size of the binary string: " + Num);  
if(sols != 0)  
{  
System.out.println("It contains  " + sols + " strings which are not contain successive one's.");  
}  
else  
{  
System.out.println("There isn't a binary sequence that contains successive 1.");     
}  
}  
}  

Output

The given size of the binary string: 4
It contains 8 strings which are not contain successive one's.




The given size of the binary string: 2
It contains 3 strings which are not contain successive one’s.

A single computation of each entity's value is made for the arrays dpArr[], which now has 2 * N entries. As a result, the program has an O(N), resulting in a strong (considering the asymptotic notation). Because the array dpArr[ contains 2 * N items, the program's case complexity is O(N), wherein N is the length of the digital text (again using hyperbolic nomenclature).