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:
- 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.
- If S is of length < 2, return -1.
- 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.
- If S is of length < 3, return -1.
- 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> } |
Input: S = "235".
Output: 2
Time Complexity: O(N^{2}), where N is the length of string S. As O(N) time is taken to check for the subsequence of length 1, and O(N^{2}) time is taken to check for the subsequent length 2.
Space Complexity: O(1).
Also see, Euclid GCD Algorithm