Dado un entero K y una array Q[][] que consta de N consultas de tipo {L, R} , la tarea de cada consulta es imprimir el recuento de números del rango [L, R] que no contiene el dígito K en su representación decimal u octal.
Ejemplos:
Entrada: K = 7, Q[][] = {{1, 15}}
Salida: 13
Explicación:
Solo los números 7 y 15 contienen el dígito K en sus representaciones octales o decimales.
La representación octal del número 7 es 7.
La representación octal del número 15 es 17.Entrada: K = 8, Q[][] = {{1, 10}}
Salida: 9
Explicación:
Solo el número 8 contiene el dígito K en sus representaciones decimales.
La representación octal del número 8 es 10.
Enfoque ingenuo: la idea es atravesar el rango [L, R] para cada consulta y encontrar aquellos números cuyas representaciones decimales y octales no contengan el dígito K . Imprime el recuento de dichos números.
Complejidad de tiempo: O(N 2 *(log 10 (N) + log 8 (N)))
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es calcular previamente el recuento de todos esos números utilizando la técnica Prefix Sum . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos pref[] , para almacenar el recuento de números en el rango [0, i] que contiene el dígito K en su representación octal o decimal.
- Ahora recorra el rango [0, 1e6] y realice los siguientes pasos:
- Si el número contiene el dígito K en representación octal o decimal, actualice pref[i] como pref[i – 1] + 1 .
- De lo contrario, actualice pref[i] como pref[i – 1] .
- Recorra las consultas dadas e imprima el conteo para cada consulta como
Q[i][1] – Q[i][0] + 1 – (pref[Q[i][1]] – pref[Q[i][0] – 1])
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the given digit
// 'K' is present in the decimal and octal
// representations of num or not
bool contains(int num, int K, int base)
{
// Stores if the digit exists
// or not
bool isThere = 0;
// Iterate till nums is non-zero
while (num) {
// Find the remainder
int remainder = num % base;
// If the remainder is K
if (remainder == K) {
isThere = 1;
}
num /= base;
}
return isThere;
}
// Function to count the numbers in the
// range [1, N] such that it doesn't
// contain the digit 'K' in its decimal
// and octal representation
void count(int n, int k,
vector<vector<int> > v)
{
// Stores count of numbers in the
// range [0, i] that contains the
// digit 'K' in its octal or
// decimal representation
int pref[1000005] = { 0 };
// Traverse the range [0, 1e6 + 5]
for (int i = 1; i < 1e6 + 5; i++) {
// Check if i contains the digit
// 'K' in its decimal or
// octal representation
bool present
= contains(i, k, 10)
|| contains(i, k, 8);
// Update pref[i]
pref[i] += pref[i - 1] + present;
}
// Print the answer of queries
for (int i = 0; i < n; ++i) {
cout << v[i][1] - v[i][0] + 1
- (pref[v[i][1]]
- pref[v[i][0] - 1])
<< ' ';
}
}
// Driver Code
int main()
{
int K = 7;
vector<vector<int> > Q = { { 2, 5 },
{ 1, 15 } };
int N = Q.size();
// Function Call
count(N, K, Q);
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to check if the given digit
// 'K' is present in the decimal and octal
// representations of num or not
static boolean contains(int num, int K, int Base)
{
// Stores if the digit exists
// or not
boolean isThere = false;
// Iterate till nums is non-zero
while (num > 0)
{
// Find the remainder
int remainder = num % Base;
// If the remainder is K
if (remainder == K)
{
isThere = true;
}
num /= Base;
}
return isThere;
}
// Function to count the numbers in the
// range [1, N] such that it doesn't
// contain the digit 'K' in its decimal
// and octal representation
static void count(int n, int k,
Vector<Vector<Integer> > v)
{
// Stores count of numbers in the
// range [0, i] that contains the
// digit 'K' in its octal or
// decimal representation
int[] pref = new int[1000005];
// Traverse the range [0, 1e6 + 5]
for (int i = 1; i < 1e6 + 5; i++) {
// Check if i contains the digit
// 'K' in its decimal or
// octal representation
boolean present
= contains(i, k, 10)
|| contains(i, k, 8);
// Update pref[i]
if(present)
{
pref[i] += pref[i - 1] + 1;
}
}
// Print the answer of queries
System.out.print((v.get(0).get(1) - v.get(0).get(0) +
1 - (pref[v.get(0).get(1)] -
pref[v.get(0).get(0) - 1])) + " ");
System.out.print((v.get(1).get(1) - v.get(1).get(0) -
(pref[v.get(1).get(1)] -
pref[v.get(1).get(0) - 1])) + " ");
}
// Driver code
public static void main(String[] args)
{
int K = 7;
Vector<Vector<Integer> > Q = new Vector<Vector<Integer> >();
Q.add(new Vector<Integer>());
Q.get(0).add(2);
Q.get(0).add(5);
Q.add(new Vector<Integer>());
Q.get(1).add(1);
Q.get(1).add(15);
int N = Q.size();
// Function Call
count(N, K, Q);
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python3 program for the above approach # Function to check if the given digit # 'K' is present in the decimal and octal # representations of num or not def contains(num, K, base): # Stores if the digit exists # or not isThere = 0 # Iterate till nums is non-zero while (num): # Find the remainder remainder = num % base # If the remainder is K if (remainder == K): isThere = 1 num //= base return isThere # Function to count the numbers in the # range [1, N] such that it doesn't # contain the digit 'K' in its decimal # and octal representation def count(n, k, v): # Stores count of numbers in the # range [0, i] that contains the # digit 'K' in its octal or # decimal representation pref = [0]*1000005 # Traverse the range [0, 1e6 + 5] for i in range(1, 10 ** 6 + 5): # Check if i contains the digit # 'K' in its decimal or # octal representation present = contains(i, k, 10) or contains(i, k, 8) # Update pref[i] pref[i] += pref[i - 1] + present # Print the answer of queries for i in range(n): print(v[i][1] - v[i][0] + 1- (pref[v[i][1]]- pref[v[i][0] - 1]),end=" ") # Driver Code if __name__ == '__main__': K = 7 Q = [ [ 2, 5 ], [ 1, 15 ] ] N = len(Q) # Function Call count(N, K, Q) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to check if the given digit
// 'K' is present in the decimal and octal
// representations of num or not
static bool contains(int num, int K, int Base)
{
// Stores if the digit exists
// or not
bool isThere = false;
// Iterate till nums is non-zero
while (num > 0)
{
// Find the remainder
int remainder = num % Base;
// If the remainder is K
if (remainder == K)
{
isThere = true;
}
num /= Base;
}
return isThere;
}
// Function to count the numbers in the
// range [1, N] such that it doesn't
// contain the digit 'K' in its decimal
// and octal representation
static void count(int n, int k,
List<List<int> > v)
{
// Stores count of numbers in the
// range [0, i] that contains the
// digit 'K' in its octal or
// decimal representation
int[] pref = new int[1000005];
// Traverse the range [0, 1e6 + 5]
for (int i = 1; i < 1e6 + 5; i++) {
// Check if i contains the digit
// 'K' in its decimal or
// octal representation
bool present
= contains(i, k, 10)
|| contains(i, k, 8);
// Update pref[i]
if(present)
{
pref[i] += pref[i - 1] + 1;
}
}
// Print the answer of queries
Console.Write((v[0][1] - v[0][0] + 1 - (pref[v[0][1]] - pref[v[0][0] - 1])) + " ");
Console.Write((v[1][1] - v[1][0] - (pref[v[1][1]] - pref[v[1][0] - 1])) + " ");
}
// Driver code
static void Main()
{
int K = 7;
List<List<int> > Q = new List<List<int>>();
Q.Add(new List<int>());
Q[0].Add(2);
Q[0].Add(5);
Q.Add(new List<int>());
Q[1].Add(1);
Q[1].Add(15);
int N = Q.Count;
// Function Call
count(N, K, Q);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
// Function to check if the given digit
// 'K' is present in the decimal and octal
// representations of num or not
function contains(num, K, base)
{
// Stores if the digit exists
// or not
var isThere = 0;
// Iterate till nums is non-zero
while (num) {
// Find the remainder
var remainder = num % base;
// If the remainder is K
if (remainder == K) {
isThere = 1;
}
num /= base;
}
return isThere;
}
// Function to count the numbers in the
// range [1, N] such that it doesn't
// contain the digit 'K' in its decimal
// and octal representation
function count(n, k, v)
{
// Stores count of numbers in the
// range [0, i] that contains the
// digit 'K' in its octal or
// decimal representation
var pref = Array(100005).fill(0);
// Traverse the range [0, 1e6 + 5]
for (var i = 1; i < 100005; i++) {
// Check if i contains the digit
// 'K' in its decimal or
// octal representation
var present
= contains(i, k, 10)
|| contains(i, k, 8);
// Update pref[i]
pref[i] += pref[i - 1] + present;
}
// Print the answer of queries
for (var i = 0; i < n; ++i) {
document.write( v[i][1] - v[i][0] + 1
- (pref[v[i][1]]
- pref[v[i][0] - 1])
+ ' ');
}
}
// Driver Code
var K = 7;
var Q = [ [ 2, 5 ], [1, 15 ]];
var N = Q.length;
// Function Call
count(N, K, Q);
</script>
Producción:
4 13
Complejidad de tiempo: O(N*(log 10 (N)+log 8 (N)))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA