The Largest Prime Number Possible from a Subsequence of a Binary String

Shreya Deep
Last Updated: Jun 20, 2022
Difficulty Level :
MEDIUM

Introduction

Prime numbers are numbers that are only divisible by one and themselves. A subsequence of a string is a string obtained from the original string by deleting some characters from it. A string is a binary string containing only '0' and '1' as its characters.

Also, see Data Structures.

Problem Statement

You are given a binary string, and your task is to find the largest prime number that can be obtained from a subsequence of the string. 

For example:

Input

s= “1011”

Output

11

Explanation:

Possible Prime Subsequences

 

The largest subsequence of the string, "1011", is itself a prime number(11) and is the largest prime number that can be made. Thus, 11 is the answer.

Approach 1: Brute force

The solution is quite straightforward. We find all the subsequences of the string and determine the decimal number corresponding to each subsequence. Then, we check if the number is a prime number or not. If it is, we check if it is greater than the current answer value. If yes, then update the answer value, else move on to the next. 

Steps of implementation are:

  • Input the given string
  • Declare and initialize a variable named answer to -1. This variable will contain the final answer.
  • Since the length of the string is n, the number of subsequences will be 2^n. So, loop from 1 to 2^n.
  • Declare a string temp, which stores the current subsequence.
  • Loop through 0 to n-1, and find out which indexes have a non-zero value with the subsequence number. All those indexes will be a part of the current subsequence. So add the characters present at those indexes to temp.
  • Now, the current subsequence is found. So, find out the decimal number corresponding to the current subsequence. To find out the decimal number, we call a function named "dec," which does this task. In this function:
    • Declare a variable p, which stores which index we are currently at from the back of the string.
    • Declare a variable named "ans," which will be the converted number.
    • Loop through the string and if the current character is '1', add the value of the power of that index(from the back) to the answer. 
    • Return the answer.
  • If the found number is a prime number and if it is greater than the current answer, update the answer's value. To determine if a number is prime or not, we are using the very convenient method in a function called "prime." In this function:
    • If the number is less than 1, it is not prime for sure. So, return false.
    • Iterate from 2 till the square root of the number, and if the number is divisible by any of these, then it is not prime. So, return false.
    • Else, return true.
  • Print the answer

C++ implementation

#include<bits/stdc++.h>
using namespace std;

/*
    Function that tells if the given number is prime number or not
*/
bool prime(int num){
    /*
        If the number is less than 1, it is not prime for sure. So, return false.
    */
    if(num<=1){
        return false;
    }
    /*
        Iterate from 2 till the square root of the number and if the number is divisible by any of these, then it is not prime. So, return false.
    */
    for(int i=2;i*i<=num;i++){
        if(num%i==0){
            return false;
        }
    }
    /*
        Else, return true.
    */
    return true;
}

/*
    Function that finds out the decimal number corresponding to a given binary string.
*/
int dec(string s){
    int n = s.length();
    /*
        Declare a variable p, which stores which index we are currently at from the back of the string.
    */
    int p = 0;
    /*
        Declare a variable named "ans", which will be the converted number.
    */
    int ans=  0;
    /*
        Loop through the string and if the current character is '1', add the value of power of that index(from the back) to the answer. 
    */
    for(int i=n-1;i>=0;i--){
        if(s[i]=='1'){
            ans+=(pow(2,p));
        }
        p++;
    }
    /*
        Return the answer
    */
    return ans;
}

int main()
{
    /*
        Input the given string
    */
    string s = "1011";
    /*
        Declare and initialize a variable named answer to INT_MIN. This variable will contain the final answer.
    */
    int ans = -1;
    int n = s.length();
    /*
        Since, the length of the string is n, the number of subsequences will be 2^n. So, loop from 1 to 2^n.
    */
    for(int i=1;i<(pow(2,n));i++){
        int decimal = 0;
        /*
            Declare a string temp, which stores the current subsequence.
        */
        string temp = "";
        /*
            Loop through 0 to n-1, and find out which all indexes have a non-zero and value with the subsequence number. All those indexes will be a part of the current subsequence. So add the characters present at those indexes to temp.
        */
        for(int j=0;j<n;j++){
            if(((1<<j) & (i))!=0){
                temp+=s[j];
            }
        }
        /*
            Now, the current subsequence is found. So, find out the decimal number corresponding to the current subsequence.
        */
        decimal = dec(temp);
        /*
            If the found number is a prime number and if it is greater than the current answer, then, update the value of answer.
        */
        if(prime(decimal)){
            ans = max(ans,decimal);
        }
    }
    /*
        Print the answer
    */
    cout<<ans<<endl;
    return 0;
}

Output

11

Python Implementation


# Function to check if a
# number is prime or not
def isPrime(x):
	
	if (x <= 1):
		return False

	for i in range(2, x + 1):
		if i * i > x:
			break
		
		if (x % i == 0):
			
			# Return not prime
			return False

	# If prime return true
	return True

# Function to find the largest prime
# number possible from a subsequence
def largestPrime(s):

	# Stores pairs of subsequences and
	# their respective decimal value
	vec = [["", 0]]
	
	# Stores the answer
	ans = 0

	# Traverse the string
	for i in range(len(s)):
		
		# Stores the size of the vector
		n = len(vec)

		# Traverse the vector
		for j in range(n):
			
			# Extract the current pair
			temp = vec[j]

			# Get the binary string from the pair
			str = temp[0]

			# Stores equivalent decimal values
			val = temp[1]

			# If the current character is '1'
			if (s[i] == '1'):
				
				# Add the character
				# to the subsequence
				temp[0] = str + '1'

				# Update the value by left
				# shifting the current
				# value and adding 1 to it
				temp[1] = ((val << 1) + 1)

			# If s[i]=='0'
			else:

				# Add the character
				# to the subsequence
				temp[0] = str + '0'

				# Update the value by left
				# shifting the current
				# value and adding 0 to it
				temp[1] = ((val << 1) + 0)

			# Store the subsequence in the vector
			vec.append(temp)

			# Check if the decimal
			# representation of current
			# subsequence is prime or not
			check = temp[1]

			# If prime
			if (isPrime(check)):
				
				# Update the answer
				# with the largest one
				ans = max(ans, check)
				break

	# If no prime number
	# could be obtained
	if (ans == 0):
		print(-1)
	else:
		print(int(bin(ans)[2:]))

# Driver Code
if __name__ == '__main__':
	
	# Input String
	s = "110"
	largestPrime(s)

Output

11

Java Implementation


import java.util.*;

/*
    Function that tells if the given number is prime number or not
*/

class solution{
    static boolean prime(int num){
        /*
            If the number is less than 1, it is not prime for sure. So, return false.
        */
        if(num<=1){
            return false;
        }
        /*
            Iterate from 2 till the square root of the number and if the number is divisible by any of these, then it is not prime. So, return false.
        */
        for(int i=2;i*i<=num;i++){
            if(num%i==0){
                return false;
            }
        }
        /*
            Else, return true.
        */
        return true;
    }
    
    public static void main(String[] args)
    {
        /*
            Input the given string
        */
        String s = "1011";
        /*
            Declare and initialize a variable named answer. This variable will contain the final answer.
        */
        int ans = -1;
        int n = s.length();
        /*
            Declare an ArrayList of ArrayList which stores the subsequence along with its decimal value as a string.
        */
        ArrayList<ArrayList<String>> v = new ArrayList<>();
        /*
            Add the value {"","0"} to the vector as an empty string will have value "0".
        */
        v.add(new ArrayList<String>());
        v.get(0).add("");
        v.get(0).add("0");
        /*
            Traverse through the string
        */
        for(int i=0;i<n;i++){
            /*
                Traverse through all the elements in v, and add the current character to them.
            */
            int sz = v.size();
            for(int j=0;j<sz;j++){
                /*
                    Find the value of the new string and new decimal after adding the current character
                */
                String temp = v.get(j).get(0);
                int num = Integer.parseInt(v.get(j).get(1));
                String new_string = temp;
                int new_num;
                if(s.charAt(i)=='1'){
                    new_string+='1';
                    new_num = 2*num+1;
                }
                else{
                    new_string+='0';
                    new_num = 2*num;
                }
                /*
                    Push the new string and the new num into v as an ArrayList
                */
                v.add(new ArrayList<String>());
                v.get(v.size()-1).add(new_string);
                v.get(v.size()-1).add(Integer.toString(new_num));
                /*
                    If the new number is a prime number, update the answer to the    maximum of the answer and the new number.
                */
                if(prime(new_num)){
                    ans = Math.max(ans,new_num);
                }
            }
        }
        /*
            Print the answer
        */
        System.out.println(ans);
    }
}

Output

11

Complexities

Time complexity

O(2^n * sqrt(2^n)), where n is the length of the given string.

Reason: First, the loop for the number of subsequences takes O(2^n) time. In that loop, for each number, we're looping through the string to find out which indexes have a non-zero and value with it. This takes O(n) time. Then, finding the number corresponding to the current subsequence takes another O(n) time as we're looping through the string in the "dec" function. Then, for the number found, we're finding out if it is prime or not. This takes O(sqrt(value of the number)). And since the length of the string is n, the maximum value of the number can be 2^n-1. Therefore, in the worst case, finding out if the number is prime or not takes O(sqrt(2^n-1)), which is equivalent to O(sqrt(2^n)). Therefore, the total time complexity is O((2^n)*(n+n+sqrt(2^n))) which is equivalent to O(2^n * sqrt(2^n)). 

Space complexity

O(n), where n is the length of the given string.

Reason: Only polynomial space taken is by the string "temp," which stores the current subsequence. And since the length of the subsequence can be as much as n, the space complexity is O(n). All the other spaces are constant.

Approach 2: Using C++ vector

If we see, creating a subsequence is all about whether to add the current character to the previously formed subsequences or not. For example, if s = "11011001," till index 3, "111" and "101" are some subsequences. Now, for index 4, the character is "1". Then, subsequences ending at this index can be found by adding this character to the end of the previously found subsequences. For the above example, two of the subsequences will be "1111," and "1011" as the previously found subsequences were "111" and "101". 

Therefore, if we don't want the character to be in the subsequence for each index of the string, we move on to the next subsequence. Else, we add the current character to the subsequence. So this was all about forming the subsequences. 

One more question that arises is how to find the decimal number corresponding to any subsequence?

For this, you can notice that we have their corresponding decimal value for the previously found subsequences. So, if you don't add the current character, no new subsequence is formed; therefore, no new decimal value is found. But, if we add the present character to a subsequence, we append it at the back. 

Let's see how the decimal value changes. Let's say we have a subsequence, s, with decimal value d, and the current character to add is '1'. When '1' is added to s, the subsequence formed is s1. What value will this subsequence have?

All the characters of s are getting shifted one place towards left, and one comes in the end. Therefore, the value of this subsequence will be d*2+1. If we added '0' in the end, the subsequence would be s0, and the new decimal value will be d*2. Once the decimal value is found, we can easily check if the value is prime or not. 

Steps of implementation are:

  • Input the given string
  • Declare and initialize a variable named answer to INT_MIN. This variable will contain the final answer.
  • Declare a vector of pairs that stores the subsequence and its decimal value as pair.
  • Push the value {"",0} to the vector as an empty string will have value 0.
  • Traverse through the string
  • Traverse through all the pairs in the vector v, and add the current character to them.
  • Find the new string and new decimal value after adding the current character
  • Push the new string and the new num into v as a pair
  • If the new number is a prime number, update the answer to the maximum answer and the new number. For finding out if the number is prime or not, we're calling the "prime" function. In this function:
    • If the number is less than 1, it is not prime for sure. So, return false.
    • Iterate from 2 till the square root of the number, and if the number is divisible by any of these, then it is not prime. So, return false.
    • Else, return true.
  • Print the answer.

C++ implementation

#include<bits/stdc++.h>
using namespace std;

/*
    Function that tells if the given number is prime number or not
*/
bool prime(int num){
    /*
        If the number is less than 1, it is not prime for sure. So, return false.
    */
    if(num<=1){
        return false;
    }
    /*
        Iterate from 2 till the square root of the number and if the number is divisible by any of these, then it is not prime. So, return false.
    */
    for(int i=2;i*i<=num;i++){
        if(num%i==0){
            return false;
        }
    }
    /*
        Else, return true.
    */
    return true;
}

int main()
{
    /*
        Input the given string
    */
    string s = "1011";
    /*
        Declare and initialize a variable named answer to INT_MIN. This variable will contain the final answer.
    */
    int ans = -1;
    int n = s.length();
    /*
        Declare a vector of pairs which stores the subsequence along with its decimal value as a pair.
    */
    vector<pair<string,int>>v;
    /*
        Push the value {"",0} to the vector as an empty string will have value 0.
    */
    v.push_back({"",0});
    /*
        Traverse through the string
    */
    for(int i=0;i<n;i++){
        /*
            Traverse through all the pairs in the vector v, and add the current character to them.
        */
        int sz = v.size();
        for(int j=0;j<sz;j++){
            /*
                Find the value of the new string and new decimal after adding the current character
            */
            string temp = v[j].first;
            int num = v[j].second;
            string new_string = temp;
            int new_num;
            if(s[i]=='1'){
                new_string+='1';
                new_num = 2*num+1;
            }
            else{
                new_string+='0';
                new_num = 2*num;
            }
            /*
                Push the new string and the new num into v as a pair
            */
            v.push_back({new_string,new_num});
            /*
                If the new number is a prime number, update the answer to the    maximum of the answer and the new number.
            */
            if(prime(new_num)){
                ans = max(ans,new_num);
            }
        }
    }
    /*
        Print the answer
    */
    cout<<ans<<endl;
    return 0;
}

Output

11

Complexities

Time complexity

O(2^n*(sqrt(2^n))), where n is the length of the input string.

Reason: The outer for loop takes O(n) time. In each iteration, we're iterating over the vector and the size of the vector is 2^i. Thus, through all the iterations, this loop runs Σ2^i from i=0 to i=n-1. This will be equal to 2^n-1. And for each v[i], we're checking if the new number is prime or not. This takes O(sqrt(2^n)) time, as the maximum value of the decimal number corresponding to a subsequence having n-bits will be 2^n-1. Thus, the total time complexity is O(2^n*sqrt(2^n)). 

Space complexity

O(2^n *n), where n is the length of the input string.

Reason: The space taken up by the vector v is equal to O(2^n) as there is a total of 2^n subsequences. And we're making a copy of the subsequence once each, in the string temp and new_string. This takes at most O(n) space. Thus, the total space complexity is O(2^n*n). 

Frequently Asked Questions

What is a subsequence?

A subsequence of a string is a new string that can be derived from the original string by deleting some characters (can be none) without changing the relative ordering of other characters.

What is a prime number?

A number that is only divisible by 1 and itself is called a prime number.

What is a binary string?

A string consisting of characters' 1' and '0' is called a binary string.

Conclusion

This article discussed the problem of finding the largest prime number possible from a subsequence of a binary string. This problem required a good understanding of a string's subsequence. 

There can be many problems made around the subsequences of a string some of which are longest increasing subsequencemaximal and subsequencesdistinct subsequencescount subsequenceslongest repeating subsequencelongest common subsequence, and common digit longest subsequence

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and Interview Experiences curated by top Industry Experts only on  CodeStudio.

Happy Coding!

Was this article helpful ?
0 upvotes