Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
2.
Solution
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

Find the Length of Smallest Non-Prime Subsequence in a Numeric String

Author GAZAL ARORA
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Problem

Given a string S of integers [1, 9]. Print the length of the smallest non-prime subsequence of the string S. Print "-1" if all the subsequences are prime.

A non-prime subsequence is a subsequence such that it is not a prime number. Non-prime numbers are composite numbers that have more than two factors. These numbers can also be divided by other numbers except one and itself.

For example, 27, 24, 74, 274 are the non-prime subsequences of the string 274.

 

Input: A string S.

Output: Print the length of the smallest non-prime subsequence of the string S
 

Example,

1.

Input: S = "235"

Output: 2

Explanation:There are seven non-empty subsequences {"2", "3", "5", "23", "25", "35", "235"}. Among these subsequences, four subsequences are not prime, i.e., "23", "25", "35", and "235". Thus the smallest non-prime subsequence of the string S is "25" of length 2.

 

2.

Input: S = "14"

Output: 1

Explanation: There are three non-empty subsequences {"1", "4", "14"}. Among these subsequences, three subsequences are not prime, i.e., "1", "4", and "14". Thus the smallest non-prime subsequence of the string S is "1" of length 1. 

 

3.

Input: S = "23"

Output: -1

 

 


 

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 


 

Recommended: Try to solve it yourself before moving on to the solution.

Solution

 

Algorithm:

  1. The smallest possible length of the non-prime subsequence is 1. The prime numbers with length 1 are 2, 3, 5, 7. Now while iterating over the string S, return 1 if we find a subsequence of length 1 with a non-prime digit.
  2. If S is of length < 2, return -1.
  3. If the answer is not 1, it implies all the digits in the string S are 2, 3, 5, or 7. The prime numbers of length 2 with digits 2, 3, 5, and 7 are 23, 37, 53, and 73. Now iterate over the subsequence of length 2 and check if the subsequence is not one of these:  23, 37, 53, and 73, return 2.
  4. If S is of length < 3, return -1.
  5. There is no prime number with length 3 and digits 2, 3, 5, and 7. Therefore return 3 as an answer.

 

C++

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

// Function to return the length of the smallest non-prime subsequence.
int smallestLength(string s)
{
    // Checking for a subsequence of length 1.
    for (int i = 0; i < s.length(); i++)
    {
        // If a non-prime subsequence of length 1 is found, return 1.
        if (s[i] != '2' && s[i] != '3' && s[i] != '5' && s[i] != '7')
        {
            return 1;
        }
    }

    if( s.length() == 1)
        return -1;

    // Checking for a subsequence of length 2.
    for (int i= 0; i < s.length() - 1; i++)
    {
        for (int j = i + 1; j < s.length(); j++)
        {
            string num = to_string(s[i] + s[j]);

            // If a non prime subsequence of length 2 is found, return 2.
            if (num != "23" && num != "37" && num != "53" && num != "73")
            {
                return 2;
            }
        }

     }

    // Return 3 if length of S is >= 3 as no subsequence of length 3 // with digits 2, 3, 5, and 7 is prime.
    if( s.length() >= 3)
        return 3;
    
    return -1;
}

int main()
{
    string S = "235";
    cout<<smallestLength(S);
    return 0;
}

 

Input: S = "235".

Output: 2

Time Complexity: O(N2), where N is the length of string S. As O(N) time is taken to check for the subsequence of length 1, and O(N2) time is taken to check for the subsequent length 2.
 

Space Complexity: O(1). 

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. What is a subsequence in a string?
    A subsequence in a string is a new string formed from the original string by removing some (or none) of the characters without affecting the relative ordering of the remaining characters. (For example, "abb" is a subsequence of "aabbcc," but "acb" is not.)
     
  2. What is a prime string?
    Prime string is a string that is a prime number when converted into its numeric form. A prime number is a number that is divisible only by 1 and the number itself. For example, 2, 3, 5, 7, 11, 13 are all prime numbers.

Key Takeaways

In this article, we designed an algorithm to find the length of the smallest non-prime subsequence in a given numeric string S.

The algorithm's time complexity is O(N2), where n is the length of string S, and the space complexity is O(1).

Recommended Problems:

Use Coding Ninjas Studio to practice various DSA questions asked in many interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

 

Previous article
Check if Count of 1s can be Made Greater in a Binary string by Changing 0s Adjacent to 1s
Next article
The Largest Prime Number Possible from a Subsequence of a Binary String
Live masterclass