Dados dos números enteros L y R que denotan un rango [L, R]. La tarea es encontrar el conteo total de números en el rango dado [L,R] cuya suma de dígitos pares es mayor que la suma de dígitos impares. Ejemplos:
Entrada: L=2 R=10 Salida: 4 Los números que tienen la propiedad de que la suma de los dígitos pares es mayor que la suma de los dígitos impares son: 2, 4, 6, 8 Entrada: L=2 R=17 Salida: 7
Requisitos previos: Método Digit-DP : en primer lugar, cuente los números requeridos hasta R, es decir, en el rango [0, R]. Para llegar a la respuesta en el rango [L, R] resuelva el rango de cero a R y luego reste la respuesta para el rango de cero a L – 1. Defina los estados de DP de la siguiente manera:
- Considere el 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 de 0 a 18 si se trata de números hasta 10^18. En cada llamada recursiva, intente 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 pares que se han colocado hasta ahora.
- El segundo estado es la suma de los dígitos impares que se han colocado hasta el momento.
- 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 el dígito en la posición actual en R.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to count number in the range
// having the sum of even digits greater
// than the sum of odd digits
#include <bits/stdc++.h>
// as the number can be up to 10^18
#define int long long
using namespace std;
vector<int> v;
int dp[18][180][180][2];
int memo(int index, int evenSum,
int oddSum, int tight)
{
// Base Case
if (index == v.size()) {
// check if condition satisfied or not
if (evenSum > oddSum)
return 1;
else
return 0;
}
// If this result is already computed
// simply return it
if (dp[index][evenSum][oddSum][tight] != -1)
return dp[index][evenSum][oddSum][tight];
// Maximum limit upto which we can place
// digit. If tight is 0, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight) ? v[index] : 9;
int ans = 0;
for (int d = 0; d <= limit; d++) {
int currTight = 0;
if (d == v[index])
currTight = tight;
// if current digit is odd
if (d % 2 != 0)
ans += memo(index + 1, evenSum,
oddSum + d, currTight);
// if current digit is even
else
ans += memo(index + 1, evenSum + d,
oddSum, currTight);
}
dp[index][evenSum][oddSum][tight] = ans;
return ans;
}
// Function to convert n into its
// digit vector and uses memo() function
// to return the required count
int CountNum(int n)
{
v.clear();
while (n) {
v.push_back(n % 10);
n = n / 10;
}
reverse(v.begin(), v.end());
// Initialize DP
memset(dp, -1, sizeof(dp));
return memo(0, 0, 0, 1);
}
// Driver Code
int32_t main()
{
int L, R;
L = 2;
R = 10;
cout << CountNum(R) - CountNum(L - 1) << "\n";
return 0;
}
Java
// Java code to count number in the range
// having the sum of even digits greater
// than the sum of odd digits
import java.util.*;
class GFG
{
static Vector<Integer> v = new Vector<>();
static int[][][][] dp = new int[18][180][180][2];
static int memo(int index, int evenSum,
int oddSum, int tight)
{
// Base Case
if (index == v.size())
{
// check if condition satisfied or not
if (evenSum > oddSum)
{
return 1;
}
else
{
return 0;
}
}
// If this result is already computed
// simply return it
if (dp[index][evenSum][oddSum][tight] != -1)
{
return dp[index][evenSum][oddSum][tight];
}
// Maximum limit upto which we can place
// digit. If tight is 0, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight > 0) ? v.get(index) : 9;
int ans = 0;
for (int d = 0; d <= limit; d++)
{
int currTight = 0;
if (d == v.get(index))
{
currTight = tight;
}
// if current digit is odd
if (d % 2 != 0)
{
ans += memo(index + 1, evenSum,
oddSum + d, currTight);
} // if current digit is even
else
{
ans += memo(index + 1, evenSum + d,
oddSum, currTight);
}
}
dp[index][evenSum][oddSum][tight] = ans;
return ans;
}
// Function to convert n into its
// digit vector and uses memo() function
// to return the required count
static int CountNum(int n)
{
v.clear();
while (n > 0)
{
v.add(n % 10);
n = n / 10;
}
Collections.reverse(v);
// Initialize DP
for (int i = 0; i < 18; i++)
{
for (int j = 0; j < 180; j++)
{
for (int k = 0; k < 180; k++)
{
for (int l = 0; l < 2; l++)
{
dp[i][j][k][l] = -1;
}
}
}
}
return memo(0, 0, 0, 1);
}
// Driver Code
public static void main(String[] args)
{
int L, R;
L = 2;
R = 10;
System.out.println(CountNum(R) - CountNum(L - 1));
}
}
// This code is contributed by Princi Singh
Python3
# Python code to count number in the range # having the sum of even digits greater # than the sum of odd digits def memo(index, evenSum, oddSum, tight): # Base Case if index == len(v): # check if condition satisfied or not if evenSum > oddSum: return 1 else: return 0 # If this result is already computed # simply return it if dp[index][evenSum][oddSum][tight] != -1: return dp[index][evenSum][oddSum][tight] # Maximum limit upto which we can place # digit. If tight is 0, means number has # already become smaller so we can place # any digit, otherwise num[index] limit = v[index] if tight else 9 ans = 0 for d in range(limit + 1): currTight = 0 if d == v[index]: currTight = tight # if current digit is odd if d % 2 != 0: ans += memo(index + 1, evenSum, oddSum + d, currTight) # if current digit is even else: ans += memo(index + 1, evenSum + d, oddSum, currTight) dp[index][evenSum][oddSum][tight] = ans return ans # Function to convert n into its digit vector # and uses memo() function to return the # required count def countNum(n): global dp, v v.clear() num = [] while n: v.append(n % 10) n //= 10 v.reverse() # Initialize dp dp = [[[[-1, -1] for i in range(180)] for j in range(180)] for k in range(18)] return memo(0, 0, 0, 1) # Driver Code if __name__ == "__main__": dp = [] v = [] L = 2 R = 10 print(countNum(R) - countNum(L - 1)) # This code is contributed by # sanjeev2552
C#
// C# code to count number in the range
// having the sum of even digits greater
// than the sum of odd digits
using System.Collections.Generic;
using System;
class GFG
{
static List<int> v = new List<int>();
static int [,,,]dp = new int[18,180,180,2];
static int memo(int index, int evenSum,
int oddSum, int tight)
{
// Base Case
if (index == v.Count)
{
// check if condition satisfied or not
if (evenSum > oddSum)
{
return 1;
}
else
{
return 0;
}
}
// If this result is already computed
// simply return it
if (dp[index,evenSum,oddSum,tight] != -1)
{
return dp[index,evenSum,oddSum,tight];
}
// Maximum limit upto which we can place
// digit. If tight is 0, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight > 0) ? v[index] : 9;
int ans = 0;
for (int d = 0; d <= limit; d++)
{
int currTight = 0;
if (d == v[index])
{
currTight = tight;
}
// if current digit is odd
if (d % 2 != 0)
{
ans += memo(index + 1, evenSum,
oddSum + d, currTight);
} // if current digit is even
else
{
ans += memo(index + 1, evenSum + d,
oddSum, currTight);
}
}
dp[index,evenSum,oddSum,tight] = ans;
return ans;
}
// Function to convert n into its
// digit vector and uses memo() function
// to return the required count
static int CountNum(int n)
{
v.Clear();
while (n > 0)
{
v.Add(n % 10);
n = n / 10;
}
v.Reverse();
// Initialize DP
for (int i = 0; i < 18; i++)
{
for (int j = 0; j < 180; j++)
{
for (int k = 0; k < 180; k++)
{
for (int l = 0; l < 2; l++)
{
dp[i,j,k,l] = -1;
}
}
}
}
return memo(0, 0, 0, 1);
}
// Driver Code
public static void Main(String[] args)
{
int L, R;
L = 2;
R = 10;
Console.WriteLine(CountNum(R) - CountNum(L - 1));
}
}
/* This code is contributed by PrinciRaj1992 */
Producción:
4
Complejidad de tiempo: Habría un máximo de 18*(180)*(180)*2 cálculos cuando 0 < a,b < 10 18
Espacio auxiliar: O(18*180*180*2), ya que estamos usando espacio extra.
Publicación traducida automáticamente
Artículo escrito por RishabhKejariwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA