Dados dos números enteros L y R , la tarea es encontrar el conteo de números en el rango [L, R] que tienen dígitos primos en las posiciones principales y dígitos no primos en las posiciones no primas.
Ejemplos:
Entrada: L = 5, R = 22
Salida: 7
Explicación: Los números 6, 8, 9, 12, 13, 15 y 17 tienen dígitos primos en las posiciones principales y dígitos no primos en las posiciones no primas.Entrada: L = 20, R = 29
Salida: 0
Explicación: No hay números que tengan dígitos primos en las posiciones principales y dígitos no primos en las posiciones no primas.
Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre el rango [L, R] . Para cada i -ésimo número, verifique si los dígitos del número son primos en las posiciones principales y no primos en las posiciones no primas o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo obtenido.
Complejidad de tiempo: O(R – L + 1) * sqrt(R) * log 10 (R)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar Digit DP . A continuación se muestra la relación de recurrencia entre los estados de programación dinámica:
Si i es primo en los dígitos primos o no primo en los dígitos no primos, entonces x = 1
pos: almacena la posición de los dígitos
primos: verifica si los dígitos primos están presentes en las posiciones principales y si los dígitos no primos en las posiciones no son primos. presente o no.
st: comprueba si un número contiene algún 0 inicial
. end: máximo de dígitos posibles en la posición actual
Siga los pasos a continuación para resolver el problema:
- Inicialice una array 4D, digamos dp[pos][st][tight][prime] .
- Calcule el valor de dp[pos][st][tight][prime] para el número R utilizando la memorización , digamos cntR .
- Calcule el valor de dp[pos][st][tight][prime] para el número L – 1 utilizando la memorización , digamos cntL .
- Finalmente, imprima el valor de (cntR – cntL) .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Store digits of a number
vector<long long int> num;
// Store overlapping subproblems
long long int dp[19][2][2][19];
// Function to check if a
// number is prime or not
bool isPrime(long long int n)
{
// If n is less than
// or equal to 1
if (n <= 1)
return false;
// If n is less than
// or equal to 3
if (n <= 3)
return true;
// If n is a multiple of 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Iterate over the range [5, n]
for (long long int i = 5; i * i <= n;
i = i + 6) {
// If n is a multiple of i or (i + 2)
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to count the required
// numbers from the given range
long long cntNum(long long pos, long long st,
long long tight, long long prime)
{
// Base Case
if (pos == num.size())
return 1;
// If the subproblems already computed
if (dp[pos][st][tight][prime] != -1)
return dp[pos][st][tight][prime];
long long int res = 0;
// Stores maximum possible
// at current digits
long long end = (tight == 0) ? num[pos] : 9;
// Iterate over all possible digits
// at current position
for (long long i = 0; i <= end; i++) {
// Check if i is the maximum possible
// digit at current position or not
long long ntight = (i < end) ? 1 : tight;
// Check if a number contains
// leading 0s or not
long long int nzero = (i != 0) ? 1 : st;
// If number has only leading zeros
// and digit is non-zero
if ((nzero == 1) && isPrime(i) && isPrime(prime)) {
// Prime digits at prime positions
res += cntNum(pos + 1, nzero,
ntight, prime + 1);
}
if ((nzero == 1) && !isPrime(i) && !isPrime(prime)) {
// Non-prime digits at
// non-prime positions
res += cntNum(pos + 1, nzero,
ntight, prime + 1);
}
// If the number has only leading zeros
// and i is zero,
if (nzero == 0)
res += cntNum(pos + 1, nzero,
ntight, prime);
}
return dp[pos][st][tight][prime] = res;
}
// Function to find count of numbers in
// range [0, b] whose digits are prime
// at prime and non-prime at non-prime pos
long long int cntZeroRange(long long int b)
{
num.clear();
// Insert digits of a number, b
while (b > 0) {
num.push_back(b % 10);
b /= 10;
}
// Reversing the digits in num
reverse(num.begin(), num.end());
// Initializing dp with -1
memset(dp, -1, sizeof(dp));
long long int res = cntNum(0, 0, 0, 1);
// Returning the value
return res;
}
// Driver Code
int main()
{
// Given range, [L, R]
long long int L = 5, R = 22;
// Function Call
long long int res
= cntZeroRange(R) - cntZeroRange(L - 1);
// Print answer
cout << res << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Store digits of a number
static Vector<Integer> num = new Vector<>();
// Store overlapping subproblems
static int [][][][]dp = new int[19][2][2][19];
// Function to check if a
// number is prime or not
static boolean isPrime(int n)
{
// If n is less than
// or equal to 1
if (n <= 1)
return false;
// If n is less than
// or equal to 3
if (n <= 3)
return true;
// If n is a multiple of 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Iterate over the range [5, n]
for (int i = 5; i * i <= n;
i = i + 6) {
// If n is a multiple of i or (i + 2)
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to count the required
// numbers from the given range
static int cntNum(int pos, int st,
int tight, int prime)
{
// Base Case
if (pos == num.size())
return 1;
// If the subproblems already computed
if (dp[pos][st][tight][prime] != -1)
return dp[pos][st][tight][prime];
int res = 0;
// Stores maximum possible
// at current digits
int end = (tight == 0) ? num.get(pos) : 9;
// Iterate over all possible digits
// at current position
for (int i = 0; i <= end; i++)
{
// Check if i is the maximum possible
// digit at current position or not
int ntight = (i < end) ? 1 : tight;
// Check if a number contains
// leading 0s or not
int nzero = (i != 0) ? 1 : st;
// If number has only leading zeros
// and digit is non-zero
if ((nzero == 1) && isPrime(i) && isPrime(prime)) {
// Prime digits at prime positions
res += cntNum(pos + 1, nzero,
ntight, prime + 1);
}
if ((nzero == 1) && !isPrime(i) && !isPrime(prime)) {
// Non-prime digits at
// non-prime positions
res += cntNum(pos + 1, nzero,
ntight, prime + 1);
}
// If the number has only leading zeros
// and i is zero,
if (nzero == 0)
res += cntNum(pos + 1, nzero,
ntight, prime);
}
return dp[pos][st][tight][prime] = res;
}
// Function to find count of numbers in
// range [0, b] whose digits are prime
// at prime and non-prime at non-prime pos
static int cntZeroRange(int b)
{
num.clear();
// Insert digits of a number, b
while (b > 0) {
num.add(b % 10);
b /= 10;
}
// Reversing the digits in num
Collections.reverse(num);
// Initializing dp with -1
for (int i = 0; i < 19; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
for (int l = 0; l < 19; l++)
dp[i][j][k][l] = -1;
int res = cntNum(0, 0, 0, 1);
// Returning the value
return res;
}
// Driver Code
public static void main(String[] args)
{
// Given range, [L, R]
int L = 5, R = 22;
// Function Call
int res
= cntZeroRange(R) - cntZeroRange(L - 1);
// Print answer
System.out.print(res +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach from math import ceil, sqrt # Function to check if a # number is prime or not def isPrime(n): # If n is less than # or equal to 1 if (n <= 1): return False # If n is less than # or equal to 3 if (n <= 3): return True # If n is a multiple of 2 or 3 if (n % 2 == 0 or n % 3 == 0): return False # Iterate over the range [5, n] for i in range(5, ceil(sqrt(n)), 6): # If n is a multiple of i or (i + 2) if (n % i == 0 or n % (i + 2) == 0): return False return True # Function to count the required # numbers from the given range def cntNum(pos, st, tight, prime): global dp, num if (pos == len(num)): return 1 # If the subproblems already computed if (dp[pos][st][tight][prime] != -1): return dp[pos][st][tight][prime] res = 0 # Stores maximum possible # at current digits end = num[pos] if (tight == 0) else 9 # Iterate over all possible digits # at current position for i in range(end + 1): # Check if i is the maximum possible # digit at current position or not ntight = 1 if (i < end) else tight # Check if a number contains # leading 0s or not nzero = 1 if (i != 0) else st # If number has only leading zeros # and digit is non-zero if ((nzero == 1) and isPrime(i) and isPrime(prime)): # Prime digits at prime positions res += cntNum(pos + 1, nzero, ntight, prime + 1) if ((nzero == 1) and isPrime(i) == False and isPrime(prime) == False): # Non-prime digits at # non-prime positions res += cntNum(pos + 1, nzero, ntight, prime + 1) # If the number has only leading zeros # and i is zero, if (nzero == 0): res += cntNum(pos + 1, nzero, ntight, prime) dp[pos][st][tight][prime] = res return dp[pos][st][tight][prime] # Function to find count of numbers in # range [0, b] whose digits are prime # at prime and non-prime at non-prime pos def cntZeroRange(b): global num, dp num.clear() while (b > 0): num.append(b % 10) b //= 10 # Reversing the digits in num num = num[::-1] # print(num) dp = [[[[-1 for i in range(19)] for i in range(2)] for i in range(2)] for i in range(19)] res = cntNum(0, 0, 0, 1) # Returning the value return res # Driver Code if __name__ == '__main__': dp = [[[[-1 for i in range(19)] for i in range(2)] for i in range(2)] for i in range(19)] L, R, num = 5, 22, [] # Function Call res = cntZeroRange(R) - cntZeroRange(L - 1) # Print answer print(res) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Store digits of a number
static List<int> num = new List<int>();
// Store overlapping subproblems
static int[, , , ] dp = new int[19, 2, 2, 19];
// Function to check if a
// number is prime or not
static bool isPrime(int n)
{
// If n is less than
// or equal to 1
if (n <= 1)
return false;
// If n is less than
// or equal to 3
if (n <= 3)
return true;
// If n is a multiple of 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Iterate over the range [5, n]
for (int i = 5; i * i <= n; i = i + 6) {
// If n is a multiple of i or (i + 2)
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to count the required
// numbers from the given range
static int cntNum(int pos, int st, int tight, int prime)
{
// Base Case
if (pos == num.Count)
return 1;
// If the subproblems already computed
if (dp[pos, st, tight, prime] != -1)
return dp[pos, st, tight, prime];
int res = 0;
// Stores maximum possible
// at current digits
int end = (tight == 0) ? num[pos] : 9;
// Iterate over all possible digits
// at current position
for (int i = 0; i <= end; i++) {
// Check if i is the maximum possible
// digit at current position or not
int ntight = (i < end) ? 1 : tight;
// Check if a number contains
// leading 0s or not
int nzero = (i != 0) ? 1 : st;
// If number has only leading zeros
// and digit is non-zero
if ((nzero == 1) && isPrime(i)
&& isPrime(prime)) {
// Prime digits at prime positions
res += cntNum(pos + 1, nzero, ntight,
prime + 1);
}
if ((nzero == 1) && !isPrime(i)
&& !isPrime(prime)) {
// Non-prime digits at
// non-prime positions
res += cntNum(pos + 1, nzero, ntight,
prime + 1);
}
// If the number has only leading zeros
// and i is zero,
if (nzero == 0)
res += cntNum(pos + 1, nzero, ntight,
prime);
}
return dp[pos, st, tight, prime] = res;
}
// Function to find count of numbers in
// range [0, b] whose digits are prime
// at prime and non-prime at non-prime pos
static int cntZeroRange(int b)
{
num.Clear();
// Insert digits of a number, b
while (b > 0) {
num.Add(b % 10);
b /= 10;
}
// Reversing the digits in num
num.Reverse();
// Initializing dp with -1
for (int i = 0; i < 19; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
for (int l = 0; l < 19; l++)
dp[i, j, k, l] = -1;
int res = cntNum(0, 0, 0, 1);
// Returning the value
return res;
}
// Driver Code
public static void Main(string[] args)
{
// Given range, [L, R]
int L = 5, R = 22;
// Function Call
int res = cntZeroRange(R) - cntZeroRange(L - 1);
// Print answer
Console.WriteLine(res + "\n");
}
}
// This code is contributed by chitranayal.
Javascript
<script>
// JavaScript program for the above approach
// Store digits of a number
let num = [];
// Store overlapping subproblems
let dp = new Array(19);
// Function to check if a
// number is prime or not
function isPrime(n)
{
// If n is less than
// or equal to 1
if (n <= 1)
return false;
// If n is less than
// or equal to 3
if (n <= 3)
return true;
// If n is a multiple of 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Iterate over the range [5, n]
for (let i = 5; i * i <= n;
i = i + 6) {
// If n is a multiple of i or (i + 2)
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to count the required
// numbers from the given range
function cntNum(pos,st,tight,prime)
{
// Base Case
if (pos == num.length)
return 1;
// If the subproblems already computed
if (dp[pos][st][tight][prime] != -1)
return dp[pos][st][tight][prime];
let res = 0;
// Stores maximum possible
// at current digits
let end = (tight == 0) ? num[pos] : 9;
// Iterate over all possible digits
// at current position
for (let i = 0; i <= end; i++)
{
// Check if i is the maximum possible
// digit at current position or not
let ntight = (i < end) ? 1 : tight;
// Check if a number contains
// leading 0s or not
let nzero = (i != 0) ? 1 : st;
// If number has only leading zeros
// and digit is non-zero
if ((nzero == 1) && isPrime(i) && isPrime(prime)) {
// Prime digits at prime positions
res += cntNum(pos + 1, nzero,
ntight, prime + 1);
}
if ((nzero == 1) && !isPrime(i) && !isPrime(prime)) {
// Non-prime digits at
// non-prime positions
res += cntNum(pos + 1, nzero,
ntight, prime + 1);
}
// If the number has only leading zeros
// and i is zero,
if (nzero == 0)
res += cntNum(pos + 1, nzero,
ntight, prime);
}
return dp[pos][st][tight][prime] = res;
}
// Function to find count of numbers in
// range [0, b] whose digits are prime
// at prime and non-prime at non-prime pos
function cntZeroRange(b)
{
num=[];
// Insert digits of a number, b
while (b > 0) {
num.push(b % 10);
b = Math.floor(b/10);
}
// Reversing the digits in num
num.reverse();
for(let i=0;i<19;i++)
{
dp[i]=new Array(2);
for(let j=0;j<2;j++)
{
dp[i][j]=new Array(2);
for(let k=0;k<2;k++)
{
dp[i][j][k]=new Array(19);
for(let l=0;l<19;l++)
{
dp[i][j][k][l]=-1;
}
}
}
}
let res = cntNum(0, 0, 0, 1);
// Returning the value
return res;
}
// Driver Code
// Given range, [L, R]
let L = 5, R = 22;
// Function Call
let res
= cntZeroRange(R) - cntZeroRange(L - 1);
// Print answer
document.write(res +"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
7
Complejidad de tiempo: O(log 10 (R) * log 10 (L) sqrt(log 10 (R))* 10 * 4))
Espacio auxiliar: O(log 10 (R) * log 10 (L) * 4)
Publicación traducida automáticamente
Artículo escrito por PratikLath y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA