Dado un rango [L, R] . La tarea es contar los números en el rango que tiene una diferencia entre la suma de los dígitos en la posición par y la suma de los dígitos en la posición impar es un número primo. Considere la posición del dígito menos significativo en el número como una posición impar.
Ejemplos:
Input : L = 1, R = 50 Output : 6 Explanation : Only, 20, 30, 31, 41, 42 and 50 are valid numbers. Input : L = 50, R = 100 Output : 18
Requisitos previos: enfoque de dígitos DP : en primer lugar, si somos capaces de contar los números requeridos hasta R, es decir, en el rango [0, R], podemos llegar fácilmente a nuestra respuesta en el rango [L, R] resolviendo de cero a R y luego restando la respuesta que obtenemos después de resolver de cero a L – 1. Ahora, necesitamos definir los estados de DP. Estados DP:
- Dado que podemos considerar nuestro número como una secuencia de dígitos, un estado es la posición en la que nos encontramos actualmente. Esta posición puede tener valores del 0 al 18 si se trata de números hasta el 10 18 . En cada llamada recursiva, tratamos de construir la secuencia de izquierda a derecha colocando un dígito del 0 al 9.
- El primer estado es la suma de los dígitos en las posiciones pares que hemos colocado hasta ahora.
- El segundo estado es la suma de los dígitos en posiciones impares que hemos colocado hasta ahora.
- Otro estado es la variable booleana tight que indica que el número que estamos tratando de construir ya se ha vuelto más pequeño que R, de modo que en las próximas llamadas recursivas podemos colocar cualquier dígito del 0 al 9. Si el número no se ha vuelto más pequeño, el límite máximo de dígito que podemos colocar es dígito en la posición actual en R.
Además, cuando alcancemos la condición base, debemos verificar si la diferencia requerida es un número primo o no. Dado que el número más alto en el rango es 10 18 , la suma máxima en posiciones pares o impares puede ser un máximo de 9 veces 9 y, por lo tanto, la diferencia máxima. Por lo tanto, solo debemos verificar los números primos hasta el 100 en la condición base.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
const int M = 18;
int a, b, dp[M][90][90][2];
// Prime numbers upto 100
int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97 };
// Function to return the count of
// required numbers from 0 to num
int count(int pos, int even, int odd, int tight,
vector<int> num)
{
// Base Case
if (pos == num.size()) {
if (num.size() & 1)
swap(odd, even);
int d = even - odd;
// check if the difference is equal
// to any prime number
for (int i = 0; i < 24; i++)
if (d == prime[i])
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][even][odd][tight] != -1)
return dp[pos][even][odd][tight];
int ans = 0;
// Maximum limit upto which we can place
// digit. If tight is 1, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight ? 9 : num[pos]);
for (int d = 0; d <= limit; d++) {
int currF = tight, currEven = even;
int currOdd = odd;
if (d < num[pos])
currF = 1;
// If the current position is odd
// add it to currOdd, otherwise to
// currEven
if (pos & 1)
currOdd += d;
else
currEven += d;
ans += count(pos + 1, currEven, currOdd,
currF, num);
}
return dp[pos][even][odd][tight] = ans;
}
// Function to convert x into its digit vector
// and uses count() function to return the
// required count
int solve(int x)
{
vector<int> num;
while (x) {
num.push_back(x % 10);
x /= 10;
}
reverse(num.begin(), num.end());
// Initialize dp
memset(dp, -1, sizeof(dp));
return count(0, 0, 0, 0, num);
}
// Driver Code
int main()
{
int L = 1, R = 50;
cout << solve(R) - solve(L - 1) << endl;
L = 50, R = 100;
cout << solve(R) - solve(L - 1) << endl;
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
static int M = 18;
static int a, b, dp[][][][] = new int[M][90][90][2];
// Prime numbers upto 100
static int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97 };
// Function to return the count of
// required numbers from 0 to num
static int count(int pos, int even, int odd, int tight,
Vector<Integer> num)
{
// Base Case
if (pos == num.size())
{
if ((num.size() & 1) != 0)
{
int t = odd;
odd = even;
even = t;
}
int d = even - odd;
// check if the difference is equal
// to any prime number
for (int i = 0; i < 24; i++)
if (d == prime[i])
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][even][odd][tight] != -1)
return dp[pos][even][odd][tight];
int ans = 0;
// Maximum limit upto which we can place
// digit. If tight is 1, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight != 0 ? 9 : num.get(pos));
for (int d = 0; d <= limit; d++)
{
int currF = tight, currEven = even;
int currOdd = odd;
if (d < num.get(pos))
currF = 1;
// If the current position is odd
// add it to currOdd, otherwise to
// currEven
if ((pos & 1) != 0)
currOdd += d;
else
currEven += d;
ans += count(pos + 1, currEven, currOdd,
currF, num);
}
return dp[pos][even][odd][tight] = ans;
}
// Function to convert x into its digit vector
// and uses count() function to return the
// required count
static int solve(int x)
{
Vector<Integer> num = new Vector<Integer>();
while (x != 0)
{
num.add(x % 10);
x /= 10;
}
Collections.reverse(num);
// Initialize dp
for(int i = 0; i < dp.length; i++)
for(int j = 0; j < dp[i].length; j++)
for(int k = 0; k < dp[i][j].length; k++)
for(int k1 = 0; k1 < dp[i][j][k].length; k1++)
dp[i][j][k][k1] = -1;
return count(0, 0, 0, 0, num);
}
// Driver Code
public static void main(String args[])
{
int L = 1, R = 50;
System.out.println( solve(R) - solve(L - 1));
L = 50; R = 100;
System.out.println( solve(R) - solve(L - 1));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python implementation of the above approach M = 18 # Prime numbers upto 100 prime = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ] # Function to return the count of # required numbers from 0 to num def count(pos, even, odd, tight, num): # Base Case if pos == len(num): if len(num) & 1: odd, even = even, odd d = even - odd # check if the difference is equal # to any prime number for i in range(24): if d == prime[i]: return 1 return 0 # If this result is already computed # simply return it if dp[pos][even][odd][tight] != -1: return dp[pos][even][odd][tight] ans = 0 # Maximum limit upto which we can place # digit. If tight is 1, means number has # already become smaller so we can place # any digit, otherwise num[pos] limit = 9 if tight else num[pos] for d in range(limit + 1): currF = tight currEven = even currOdd = odd if d < num[pos]: currF = 1 # If the current position is odd # add it to currOdd, otherwise to # currEven if pos & 1: currOdd += d else: currEven += d ans += count(pos + 1, currEven, currOdd, currF, num) dp[pos][even][odd][tight] = ans return dp[pos][even][odd][tight] # Function to convert x into its digit vector # and uses count() function to return the # required count def solve(x): global dp num = [] while x: num.append(x % 10) x //= 10 num.reverse() # Initialize dp dp = [[[[-1, -1] for i in range(90)] for j in range(90)] for k in range(M)] return count(0, 0, 0, 0, num) # Driver Code if __name__ == "__main__": dp = [] L = 1 R = 50 print(solve(R) - solve(L - 1)) L = 50 R = 100 print(solve(R) - solve(L - 1)) # This code is contributed by # sanjeev2552
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int M = 18;
static int a, b;
static int [,,,]dp = new int[M, 90, 90, 2];
// Prime numbers upto 100
static int []prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97 };
// Function to return the count of
// required numbers from 0 to num
static int count(int pos, int even,
int odd, int tight,
List<int> num)
{
// Base Case
if (pos == num.Count)
{
if ((num.Count & 1) != 0)
{
int t = odd;
odd = even;
even = t;
}
int d = even - odd;
// check if the difference is equal
// to any prime number
for (int i = 0; i < 24; i++)
if (d == prime[i])
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos, even, odd, tight] != -1)
return dp[pos, even, odd, tight];
int ans = 0;
// Maximum limit upto which we can place
// digit. If tight is 1, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight != 0 ? 9 : num[pos]);
for (int d = 0; d <= limit; d++)
{
int currF = tight, currEven = even;
int currOdd = odd;
if (d < num[pos])
currF = 1;
// If the current position is odd
// add it to currOdd, otherwise to
// currEven
if ((pos & 1) != 0)
currOdd += d;
else
currEven += d;
ans += count(pos + 1, currEven,
currOdd, currF, num);
}
return dp[pos, even, odd, tight] = ans;
}
// Function to convert x into its digit vector
// and uses count() function to return the
// required count
static int solve(int x)
{
List<int> num = new List<int>();
while (x != 0)
{
num.Add(x % 10);
x /= 10;
}
num.Reverse();
// Initialize dp
for(int i = 0; i < dp.GetLength(0); i++)
for(int j = 0; j < dp.GetLength(1); j++)
for(int k = 0; k < dp.GetLength(2); k++)
for(int k1 = 0; k1 < dp.GetLength(3); k1++)
dp[i, j, k, k1] = -1;
return count(0, 0, 0, 0, num);
}
// Driver Code
public static void Main(String []args)
{
int L = 1, R = 50;
Console.WriteLine(solve(R) - solve(L - 1));
L = 50; R = 100;
Console.WriteLine(solve(R) - solve(L - 1));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the above approach
var M = 18;
var a, b;
var dp = Array.from(Array(M), ()=>Array(90));
// Prime numbers upto 100
var prime = [2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97 ];
// Function to return the count of
// required numbers from 0 to num
function count(pos, even, odd, tight, num)
{
// Base Case
if (pos == num.length) {
if (num.length & 1)
[odd, even] = [even, odd]
var d = even - odd;
// check if the difference is equal
// to any prime number
for (var i = 0; i < 24; i++)
if (d == prime[i])
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][even][odd][tight] != -1)
return dp[pos][even][odd][tight];
var ans = 0;
// Maximum limit upto which we can place
// digit. If tight is 1, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
var limit = (tight ? 9 : num[pos]);
for (var d = 0; d <= limit; d++) {
var currF = tight, currEven = even;
var currOdd = odd;
if (d < num[pos])
currF = 1;
// If the current position is odd
// add it to currOdd, otherwise to
// currEven
if (pos & 1)
currOdd += d;
else
currEven += d;
ans += count(pos + 1, currEven, currOdd,
currF, num);
}
return dp[pos][even][odd][tight] = ans;
}
// Function to convert x into its digit vector
// and uses count() function to return the
// required count
function solve(x)
{
var num = [];
while (x) {
num.push(x % 10);
x = parseInt(x/10);
}
num.reverse();
// Initialize dp
for(var i =0; i<M; i++)
for(var j =0; j<90; j++)
dp[i][j] = Array.from(Array(90), ()=>Array(2).fill(-1))
return count(0, 0, 0, 0, num);
}
// Driver Code
var L = 1, R = 50;
document.write( solve(R) - solve(L - 1) + "<br>");
L = 50, R = 100;
document.write( solve(R) - solve(L - 1));
</script>
Producción
6 18
Complejidad de tiempo: O (pos * límite)
Espacio auxiliar: O(M*90*90*2)
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA