Dados dos enteros L y R , la tarea es contar números del rango [L, R] que tienen dígitos impares en posiciones impares y dígitos pares en posiciones pares respectivamente.
Ejemplos:
Entrada: L = 3, R = 25
Salida: 9
Explicación: Los números que cumplen las condiciones son 3, 5, 7, 9, 10, 12, 14, 16 y 18.Entrada: L = 128, R = 162
Salida: 7
Explicación: Los números que cumplen las condiciones son 129, 141, 143, 145, 147, 149 y 161.
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
Se puede observar que cada posición par tiene 5 opciones {0, 2, 4, 6, 8} y cada posición impar también tiene 5 opciones {1, 3, 5, 7, 9} . Por lo tanto, hay 5 posibilidades para cada puesto. Considerando d como el número de dígitos en cualquier número que satisfaga la condición y D como el número de dígitos en N , se pueden hacer las siguientes observaciones:
- Caso 1: si d < D , entonces el recuento de números totales que consisten en d dígitos que satisfacen la condición es 5 d ya que cada número tiene 5 opciones y los números obtenidos serán todos menores que N .
- Caso 2: Si D = d , entonces el conteo de números totales que satisfacen la condición de longitud d es 5 d . Pero los números que excedan N deben descartarse, lo cual se determina de la siguiente manera:
- Para lugares pares, si el dígito en el lugar p es x , entonces (5 — (x / 2 + 1)) * 5 (D — p) los números son mayores que N .
- Para lugares impares, si el dígito en el lugar p es x , entonces (5 — (x + 1) / 2) * 5 (D — p) los números serán mayores que N .
Siga los pasos a continuación para resolver el problema:
- Defina una función countNumberUtill() para contar los números del rango [1, N], satisfaciendo la condición, donde N es un número natural.
- Inicializar una variable entera, contar y vectorizar dígitos para almacenar los dígitos del entero N .
- Recorra todos los dígitos del número dado, es decir, del 1 al D , y realice lo siguiente:
- Almacene los 5 i en variable, digamos res .
- Recorra de p = 1 a p = D y realice lo siguiente:
- Inicialice una variable x y almacene x = dígitos [p] en ella.
- Si p es par, reste (5 — (x / 2 + 1)) * 5 (D— p) de res .
- De lo contrario, reste (5 — (x + 1) / 2) * 5 (D — p) de res .
- Añadir res a la cuenta .
- Devuelve la cuenta .
- Imprima countNumberUtill(R) — countNumberUtill(L – 1) como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Function to calculate 5^p
ll getPower(int p)
{
// Stores the result
ll res = 1;
// Multiply 5 p times
while (p--) {
res *= 5;
}
// Return the result
return res;
}
// Function to count all numbers upto N
// having odd digits at odd places and
// even digits at even places
ll countNumbersUtil(ll N)
{
// Stores the count
ll count = 0;
// Stores the digits of N
vector<int> digits;
// Insert the digits of N
while (N) {
digits.push_back(N % 10);
N /= 10;
}
// Reverse the vector to arrange
// the digits from first to last
reverse(digits.begin(), digits.end());
// Stores count of digits of n
int D = digits.size();
for (int i = 1; i <= D; i++) {
// Stores the count of numbers
// with i digits
ll res = getPower(i);
// If the last digit is reached,
// subtract numbers eceeding range
if (i == D) {
// Iterate over all the places
for (int p = 1; p <= D; p++) {
// Stores the digit in the pth place
int x = digits[p - 1];
// Stores the count of numbers
// having a digit greater than x
// in the p-th position
ll tmp = 0;
// Calculate the count of numbers
// exceeding the range if p is even
if (p % 2 == 0) {
tmp = (5 - (x / 2 + 1))
* getPower(D - p);
}
// Calculate the count of numbers
// exceeding the range if p is odd
else {
tmp = (5 - (x + 1) / 2)
* getPower(D - p);
}
// Subtract the count of numbers
// exceeding the range from total count
res -= tmp;
// If the parity of p and the
// parity of x are not same
if (p % 2 != x % 2) {
break;
}
}
}
// Add count of numbers having i digits
// and satisfies the given conditions
count += res;
}
// Return the total count of numbers till n
return count;
}
// Function to calculate the count of numbers
// from given range having odd digits places
// and even digits at even places
void countNumbers(ll L, ll R)
{
// Count of numbers in range [L, R] =
// Count of numbers till R -
cout << (countNumbersUtil(R)
// Count of numbers till (L-1)
- countNumbersUtil(L - 1))
<< endl;
}
// Driver Code
int main()
{
ll L = 128, R = 162;
countNumbers(L, R);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.util.Vector;
import java.util.Collections;
class GFG{
// Function to calculate 5^p
static int getPower(int p)
{
// Stores the result
int res = 1;
// Multiply 5 p times
while (p > 0)
{
res *= 5;
p--;
}
// Return the result
return res;
}
// Function to count all numbers upto N
// having odd digits at odd places and
// even digits at even places
static int countNumbersUtil(int N)
{
// Stores the count
int count = 0;
// Stores the digits of N
Vector<Integer> digits = new Vector<Integer>();
// Insert the digits of N
while (N > 0)
{
digits.add(N % 10);
N /= 10;
}
// Reverse the vector to arrange
// the digits from first to last
Collections.reverse(digits);
// Stores count of digits of n
int D = digits.size();
for(int i = 1; i <= D; i++)
{
// Stores the count of numbers
// with i digits
int res = getPower(i);
// If the last digit is reached,
// subtract numbers eceeding range
if (i == D)
{
// Iterate over all the places
for(int p = 1; p <= D; p++)
{
// Stores the digit in the pth place
int x = digits.get(p - 1);
// Stores the count of numbers
// having a digit greater than x
// in the p-th position
int tmp = 0;
// Calculate the count of numbers
// exceeding the range if p is even
if (p % 2 == 0)
{
tmp = (5 - (x / 2 + 1)) *
getPower(D - p);
}
// Calculate the count of numbers
// exceeding the range if p is odd
else
{
tmp = (5 - (x + 1) / 2) *
getPower(D - p);
}
// Subtract the count of numbers
// exceeding the range from total count
res -= tmp;
// If the parity of p and the
// parity of x are not same
if (p % 2 != x % 2)
{
break;
}
}
}
// Add count of numbers having i digits
// and satisfies the given conditions
count += res;
}
// Return the total count of numbers till n
return count;
}
// Function to calculate the count of numbers
// from given range having odd digits places
// and even digits at even places
static void countNumbers(int L, int R)
{
// Count of numbers in range [L, R] =
// Count of numbers till R -
System.out.println(countNumbersUtil(R) -
// Count of numbers till (L-1)
countNumbersUtil(L - 1));
}
// Driver Code
public static void main(String args[])
{
int L = 128, R = 162;
countNumbers(L, R);
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program to implement # the above approach # Function to calculate 5^p def getPower(p) : # Stores the result res = 1 # Multiply 5 p times while (p) : res *= 5 p -= 1 # Return the result return res # Function to count anumbers upto N # having odd digits at odd places and # even digits at even places def countNumbersUtil(N) : # Stores the count count = 0 # Stores the digits of N digits = [] # Insert the digits of N while (N) : digits.append(N % 10) N //= 10 # Reverse the vector to arrange # the digits from first to last digits.reverse() # Stores count of digits of n D = len(digits) for i in range(1, D + 1, 1) : # Stores the count of numbers # with i digits res = getPower(i) # If the last digit is reached, # subtract numbers eceeding range if (i == D) : # Iterate over athe places for p in range(1, D + 1, 1) : # Stores the digit in the pth place x = digits[p - 1] # Stores the count of numbers # having a digit greater than x # in the p-th position tmp = 0 # Calculate the count of numbers # exceeding the range if p is even if (p % 2 == 0) : tmp = ((5 - (x // 2 + 1)) * getPower(D - p)) # Calculate the count of numbers # exceeding the range if p is odd else : tmp = ((5 - (x + 1) // 2) * getPower(D - p)) # Subtract the count of numbers # exceeding the range from total count res -= tmp # If the parity of p and the # parity of x are not same if (p % 2 != x % 2) : break # Add count of numbers having i digits # and satisfies the given conditions count += res # Return the total count of numbers tin return count # Function to calculate the count of numbers # from given range having odd digits places # and even digits at even places def countNumbers(L, R) : # Count of numbers in range [L, R] = # Count of numbers tiR - print(countNumbersUtil(R) # Count of numbers ti(L-1) - countNumbersUtil(L - 1)) # Driver Code L = 128 R = 162 countNumbers(L, R) # This code is contributed by code_hunt
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate 5^p
static int getPower(int p)
{
// Stores the result
int res = 1;
// Multiply 5 p times
while (p > 0)
{
res *= 5;
p--;
}
// Return the result
return res;
}
// Function to count all numbers upto N
// having odd digits at odd places and
// even digits at even places
static int countNumbersUtil(int N)
{
// Stores the count
int count = 0;
// Stores the digits of N
List<int> digits = new List<int>();
// Insert the digits of N
while (N > 0)
{
digits.Add(N % 10);
N /= 10;
}
// Reverse the vector to arrange
// the digits from first to last
digits.Reverse();
// Stores count of digits of n
int D = digits.Count;
for(int i = 1; i <= D; i++)
{
// Stores the count of numbers
// with i digits
int res = getPower(i);
// If the last digit is reached,
// subtract numbers eceeding range
if (i == D)
{
// Iterate over all the places
for(int p = 1; p <= D; p++)
{
// Stores the digit in the pth place
int x = digits[p - 1];
// Stores the count of numbers
// having a digit greater than x
// in the p-th position
int tmp = 0;
// Calculate the count of numbers
// exceeding the range if p is even
if (p % 2 == 0)
{
tmp = (5 - (x / 2 + 1)) *
getPower(D - p);
}
// Calculate the count of numbers
// exceeding the range if p is odd
else
{
tmp = (5 - (x + 1) / 2) *
getPower(D - p);
}
// Subtract the count of numbers
// exceeding the range from total count
res -= tmp;
// If the parity of p and the
// parity of x are not same
if (p % 2 != x % 2)
{
break;
}
}
}
// Add count of numbers having i digits
// and satisfies the given conditions
count += res;
}
// Return the total count of numbers till n
return count;
}
// Function to calculate the count of numbers
// from given range having odd digits places
// and even digits at even places
static void countNumbers(int L, int R)
{
// Count of numbers in range [L, R] =
// Count of numbers till R -
Console.WriteLine(countNumbersUtil(R) -
// Count of numbers till (L-1)
countNumbersUtil(L - 1));
}
// Driver Code
public static void Main(String[] args)
{
int L = 128, R = 162;
countNumbers(L, R);
}
}
// This code is contributed by jana_sayantan
Javascript
<script>
// JavaScript Program for the above approach
// Function to calculate 5^p
function getPower(p)
{
// Stores the result
var res = 1;
// Multiply 5 p times
while (p--) {
res *= 5;
}
// Return the result
return res;
}
// Function to count all numbers upto N
// having odd digits at odd places and
// even digits at even places
function countNumbersUtil( N)
{
// Stores the count
var count = 0;
// Stores the digits of N
var digits= [];
// Insert the digits of N
while (N) {
digits.push(N % 10);
N = parseInt(N / 10);
}
// Reverse the vector to arrange
// the digits from first to last
digits.reverse();
// Stores count of digits of n
var D = digits.length;
for (var i = 1; i <= D; i++) {
// Stores the count of numbers
// with i digits
var res = getPower(i);
// If the last digit is reached,
// subtract numbers eceeding range
if (i == D) {
// Iterate over all the places
for (var p = 1; p <= D; p++) {
// Stores the digit in the pth place
var x = digits[p - 1];
// Stores the count of numbers
// having a digit greater than x
// in the p-th position
var tmp = 0;
// Calculate the count of numbers
// exceeding the range if p is even
if (p % 2 == 0) {
tmp = (5 - parseInt(x / (2 + 1)))
* getPower(D - p);
}
// Calculate the count of numbers
// exceeding the range if p is odd
else {
tmp = (5 - parseInt( (x + 1) / 2))
* getPower(D - p);
}
// Subtract the count of numbers
// exceeding the range from total count
res -= tmp;
// If the parity of p and the
// parity of x are not same
if (p % 2 != x % 2) {
break;
}
}
}
// Add count of numbers having i digits
// and satisfies the given conditions
count += res;
}
// Return the total count of numbers till n
return count;
}
// Function to calculate the count of numbers
// from given range having odd digits places
// and even digits at even places
function countNumbers(L, R)
{
// Count of numbers in range [L, R] =
// Count of numbers till R -
document.write( (countNumbersUtil(R)
// Count of numbers till (L-1)
- countNumbersUtil(L - 1)) + "<br>");
}
var L = 128, R = 162;
countNumbers(L, R);
// This code is contributed by SoumikMondal
</script>
Producción:
7
Complejidad de tiempo: O(N 2 ), donde N es el número de dígitos en R
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sunidhichandra27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA