Dada una string S que consta de N dígitos, la tarea es encontrar el número de números primos distintos que se pueden formar usando los dígitos de la string S.
Ejemplos:
Entrada: S = «123»
Salida: 5
Explicación:
Los números primos que se pueden formar a partir de los dígitos de la string S son 2, 3, 13, 23 y 31. Por lo tanto, la cuenta total es 5.Entrada: S = “1”
Salida: 0
Enfoque: el problema dado se puede resolver utilizando la búsqueda en profundidad primero y el retroceso para encontrar todas las permutaciones posibles y verificar si se pueden formar números primos o no. Siga los pasos a continuación para resolver el problema:
- Inicialice un HashSet H para almacenar las strings de números primos únicos posibles.
- Defina una función de verificación (número de string) para verificar si el número es primo o no y realice los siguientes pasos:
- Si la longitud de la string número[] es 0, devuelve falso .
- Utilice la función recortar para recortar el número.
- Inicialice una variable larga num y almacene el número analizado en ella usando la función parseLong .
- Si num es igual a 1, devuelve false .
- Si num%2 es igual a 0 y num no es igual a 2, entonces devuelve false .
- Si num%3 es igual a 0 y num no es igual a 3, entonces devuelve false .
- Iterar sobre un rango [6, num 1/2 ] usando la variable i y realizar los siguientes pasos:
- Si num%(i-1) o num%(i+1) es igual a 0, entonces devuelve false .
- Al final, devuelve true .
- Defina una función DFS(int arr[], string ans) para encontrar todos los números primos posibles y realice los siguientes pasos:
- Llame a la función check(ans) y si la función devuelve verdadero, agregue esta string ans al HashSet H .
- Iterar sobre un rango [0, 10] usando la variable i y realizar los siguientes pasos:
- Si arr[i] es igual a 0, entonces continúa la iteración .
- Agregue el valor de i a la string de respuesta y reduzca el valor de arr[i] en 1 .
- Llame a la función DFS(arr, ans) para encontrar otras posibles respuestas retrocediendo .
- Elimine el valor de i de la string de respuesta y agregue el valor de arr[i] por 1 .
- Inicialice una array count[] de tamaño 10 para almacenar la frecuencia de cada número en la string S .
- Iterar sobre un rango [0, N] usando la variable i y realizar los siguientes pasos:
- Agregue la frecuencia por 1 a la array count[] del carácter en el i- ésimo índice en la string S.
- Llame a la función DFS(contar, “”) para encontrar todos los números primos posibles.
- Después de realizar los pasos anteriores, imprima el tamaño del HashSet H como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
#include <bits/stdc++.h>
using namespace std;
unordered_set<string> H;
// Function to check whether the
// number is prime or not
bool check(string number)
{
if (number.length() == 0) {
return false;
}
long num = stol(number);
// Condition for prime number
if (num == 1) {
return false;
}
if (num % 2 == 0 && num != 2) {
return false;
}
if (num % 3 == 0 && num != 3) {
return false;
}
// Iterate over the range [6, num]
for (int i = 6; i * i <= num; i += 6) {
if (num % (i - 1) == 0 || num % (i + 1) == 0) {
return false;
}
}
// Otherwisem return true
return true;
}
// Function to count the total number
// of prime numbers
void DFS(int arr[], string ans)
{
// Add it in the HashSet
if (check(ans)) {
H.insert(ans);
}
for (int i = 0; i <= 9; ++i) {
if (arr[i] == 0) {
continue;
}
// Use the number
ans = (ans + to_string(i));
// Decrease the number
arr[i]--;
// Perform the DFS Call
DFS(arr, ans);
ans = ans.substr(0, ans.length() - 1);
// Backtracking the frequency
arr[i]++;
}
}
// Driver Code
int main()
{
string number = "123";
int count[10];
for (int i = 0; i < 10; i++) {
count[i] = 0;
}
for (int i = 0; i < number.length(); i++) {
count[number[i] - '0']++;
}
H.clear();
DFS(count, "");
cout << H.size();
return 0;
}
// This code is contributed by maddler.
Java
// Java program for the above approach
import java.util.*;
public class GFG {
static HashSet<String> H = new HashSet<>();
// Function to check whether the
// number is prime or not
static boolean check(String number)
{
if (number.length() == 0) {
return false;
}
number = number.trim();
long num = Long.parseLong(number);
// Condition for prime number
if (num == 1) {
return false;
}
if (num % 2 == 0 && num != 2) {
return false;
}
if (num % 3 == 0 && num != 3) {
return false;
}
// Iterate over the range [6, num]
for (int i = 6; i * i <= num; i += 6) {
if (num % (i - 1) == 0 || num % (i + 1) == 0) {
return false;
}
}
// Otherwisem return true
return true;
}
// Function to count the total number
// of prime numbers
static void DFS(int arr[], String ans)
{
// Add it in the HashSet
if (check(ans) == true) {
H.add(ans);
}
for (int i = 0; i <= 9; ++i) {
if (arr[i] == 0) {
continue;
}
// Use the number
ans += i;
// Decrease the number
arr[i]--;
// Perform the DFS Call
DFS(arr, ans);
ans = ans.substring(
0, ans.length() - 1);
// Backtracking the frequency
arr[i]++;
}
}
// Driver Code
public static void main(String[] args)
{
String number = "123";
int count[] = new int[10];
for (int i = 0; i < number.length(); ++i) {
count[number.charAt(i) - 48]++;
}
// Perform the DFS Traversal
DFS(count, "");
// Print the result
System.out.println(H.size());
}
}
Python3
H = set()
# Function to check whether the
# number is prime or not
def check(number):
if (len(number) == 0):
return False
num = int(number)
# Condition for prime number
if (num == 1):
return False
if (num % 2 == 0 and num != 2):
return False
if (num % 3 == 0 and num != 3):
return False
# Iterate over the range [6, num]
i = 6
while(i * i <= num):
if (num % (i - 1) == 0 or num % (i + 1) == 0):
return False
i = i + 6
# Otherwisem return true
return True
# Function to count the total number
# of prime numbers
def DFS(arr, ans):
# Add it in the HashSet
if (check(ans)):
H.add(ans)
for i in range(10):
if (arr[i] == 0):
continue
# Use the number
ans = (ans + str(i))
# Decrease the number
arr[i] -= 1
# Perform the DFS Call
DFS(arr, ans)
ans = ans[0: len(ans) - 1]
# Backtracking the frequency
arr[i]+=1
number = "123"
count = [0]*(10)
for i in range(10):
count[i] = 0
for i in range(len(number)):
count[ord(number[i]) - ord('0')] += 1
H.clear()
DFS(count, "")
print(len(H))
# This code is contributed by divyesh072019.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
static HashSet<String> H = new HashSet<String>();
// Function to check whether the
// number is prime or not
static bool check(String number)
{
if (number.Length == 0) {
return false;
}
number = number.Trim();
long num = long.Parse(number);
// Condition for prime number
if (num == 1) {
return false;
}
if (num % 2 == 0 && num != 2) {
return false;
}
if (num % 3 == 0 && num != 3) {
return false;
}
// Iterate over the range [6, num]
for (int i = 6; i * i <= num; i += 6) {
if (num % (i - 1) == 0 || num % (i + 1) == 0) {
return false;
}
}
// Otherwisem return true
return true;
}
// Function to count the total number
// of prime numbers
static void DFS(int []arr, String ans)
{
// Add it in the HashSet
if (check(ans) == true) {
H.Add(ans);
}
for (int i = 0; i <= 9; ++i) {
if (arr[i] == 0) {
continue;
}
// Use the number
ans += i;
// Decrease the number
arr[i]--;
// Perform the DFS Call
DFS(arr, ans);
ans = ans.Substring(
0, ans.Length - 1);
// Backtracking the frequency
arr[i]++;
}
}
// Driver Code
public static void Main(String[] args)
{
String number = "123";
int []count = new int[10];
for (int i = 0; i < number.Length; ++i) {
count[number[i] - 48]++;
}
// Perform the DFS Traversal
DFS(count, "");
// Print the result
Console.WriteLine(H.Count);
}
}
// This code contributed by shikhasingrajput.
Javascript
<script>
// Javascript program for the above approach
let H = new Set();
// Function to check whether the
// number is prime or not
function check(number)
{
if (number.length == 0) {
return false;
}
let num = parseInt(number);
// Condition for prime number
if (num == 1) {
return false;
}
if (num % 2 == 0 && num != 2) {
return false;
}
if (num % 3 == 0 && num != 3) {
return false;
}
// Iterate over the range [6, num]
for (let i = 6; i * i <= num; i += 6) {
if (num % (i - 1) == 0 || num % (i + 1) == 0) {
return false;
}
}
// Otherwisem return true
return true;
}
// Function to count the total number
// of prime numbers
function DFS(arr, ans)
{
// Add it in the HashSet
if (check(ans)) {
H.add(ans);
}
for (let i = 0; i <= 9; ++i) {
if (arr[i] == 0) {
continue;
}
// Use the number
ans = (ans + i.toString());
// Decrease the number
arr[i]--;
// Perform the DFS Call
DFS(arr, ans);
ans = ans.substring(0, ans.length - 1);
// Backtracking the frequency
arr[i]++;
}
}
let number = "123";
let count = new Array(10);
for (let i = 0; i < 10; i++) {
count[i] = 0;
}
for (let i = 0; i < number.length; i++) {
count[number[i] - '0']++;
}
H.clear();
DFS(count, "");
document.write(H.size);
// This code is contributed by decode2207.
</script>
Producción:
5
Complejidad temporal: O(9 N )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA