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

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.

Input: A string S.

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

Example,

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++

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.

Live masterclass