Dada una array 2D arr[][] con cada fila de la forma de una consulta { L, R } , la tarea es contar los números en el rango [L, R] de modo que el número sea divisible por todos sus no -cero dígito.
Ejemplos:
Entrada: arr[][] ={ {1, 5}, {12, 14} }
Salida: 5 1
Explicación:
Consulta1: Todos los números en el rango [1, 5] son divisibles por sus dígitos.
Consulta 2: los números en el rango [12, 14] que son divisibles por todos sus dígitos son solo 12.Entrada: arr[][] = { {1, 20} }
Salida: 14
Explicación:
Los números en el rango [1, 20] que son divisibles por todos sus dígitos distintos de cero son: { 1, 2, 3, 4 , 5, 6, 7, 8, 9, 10, 11, 12, 15, 20}
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array arr[][] y para cada i -ésima fila de la array, iterar sobre el rango [L, R] . Para cada elemento en el rango, verifique si el número es divisible por todos sus dígitos distintos de cero o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo obtenido.
Complejidad de tiempo: O(N * (R – L)), donde N es el conteo de filas
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar encontrando el valor máximo posible de arr[i][1] y precalcular el recuento de números que es divisible por sus dígitos distintos de cero utilizando la técnica Prefix Sum . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos Max , para almacenar el valor máximo posible de arr[i][1] .
- Inicialice una array, digamos prefCntDiv[] , donde prefCntDiv[i] almacena el recuento de números del rango [1, i] que es divisible por sus dígitos distintos de cero.
- Iterar sobre el rango [1, Max] . Para cada i -ésima iteración, verifique si i es divisible por todos sus dígitos distintos de cero o no. Si se determina que es cierto, actualice prefCntDiv[i] = prefCntDiv[i – 1] + 1 .
- De lo contrario, actualice prefCntDiv[i] = prefCntDiv[i – 1] .
- Recorre la array arr[] . Para cada i -ésima fila de la array, imprima prefCntDiv[arr[i][1]] – prefCntDiv[arr[i][0] – 1].
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 Max 1000005
// Function to check if a number is divisible
// by all of its non-zero digits or not
bool CheckDivByAllDigits(int number)
{
// Stores the number
int n = number;
// Iterate over the digits
// of the numbers
while (n > 0) {
// If digit of number
// is non-zero
if (n % 10)
// If number is not divisible
// by its current digit
if (number % (n % 10)) {
return false;
}
// Update n
n /= 10;
}
return true;
}
// Function to count of numbers which are
// divisible by all of its non-zero
// digits in the range [1, i]
void cntNumInRang(int arr[][2], int N)
{
// Stores count of numbers which are
// divisible by all of its non-zero
// digits in the range [1, i]
int prefCntDiv[Max] = { 0 };
// Iterate over the range [1, Max]
for (int i = 1; i <= Max; i++) {
// Update
prefCntDiv[i] = prefCntDiv[i - 1]
+ (CheckDivByAllDigits(i));
}
// Traverse the array, arr[]
for (int i = 0; i < N; i++)
cout << (prefCntDiv[arr[i][1]]
- prefCntDiv[arr[i][0] - 1])
<< " ";
}
// Driver Code
int main()
{
int arr[][2] = { { 1, 5 }, { 12, 14 } };
int N = sizeof(arr) / sizeof(arr[0]);
cntNumInRang(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG
{
public static int Max = 1000005;
// Function to check if a number is divisible
// by all of its non-zero digits or not
static boolean CheckDivByAllDigits(int number)
{
// Stores the number
int n = number;
// Iterate over the digits
// of the numbers
while (n > 0)
{
// If digit of number
// is non-zero
if (n % 10 != 0)
// If number is not divisible
// by its current digit
if (number % (n % 10) != 0)
{
return false;
}
// Update n
n /= 10;
}
return true;
}
// Function to count of numbers which are
// divisible by all of its non-zero
// digits in the range [1, i]
static void cntNumInRang(int arr[][], int N)
{
// Stores count of numbers which are
// divisible by all of its non-zero
// digits in the range [1, i]
int prefCntDiv[] = new int[Max + 1];
// Iterate over the range [1, Max]
for (int i = 1; i <= Max; i++)
{
int ans = 0;
if (CheckDivByAllDigits(i))
ans = 1;
// Update
prefCntDiv[i] = prefCntDiv[i - 1] + ans;
}
// Traverse the array, arr[]
for (int i = 0; i < N; i++)
System.out.print((prefCntDiv[arr[i][1]]
- prefCntDiv[arr[i][0] - 1])
+ " ");
}
// Driver Code
public static void main(String[] args)
{
int arr[][] = { { 1, 5 }, { 12, 14 } };
int N = arr.length;
cntNumInRang(arr, N);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python3 program to implement # the above approach # Function to check if a number is divisible # by all of its non-zero digits or not def CheckDivByAllDigits(number): # Stores the number n = number # Iterate over the digits # of the numbers while (n > 0): # If digit of number # is non-zero if (n % 10): # If number is not divisible # by its current digit if (number % (n % 10)): return False # Update n n //= 10 return True # Function to count of numbers which are # divisible by all of its non-zero # digits in the range [1, i] def cntNumInRang(arr, N): global Max # Stores count of numbers which are # divisible by all of its non-zero # digits in the range [1, i] prefCntDiv = [0]*Max # Iterate over the range [1, Max] for i in range(1, Max): # Update prefCntDiv[i] = prefCntDiv[i - 1] + (CheckDivByAllDigits(i)) # Traverse the array, arr[] for i in range(N): print(prefCntDiv[arr[i][1]]- prefCntDiv[arr[i][0] - 1], end = " ") # Driver Code if __name__ == '__main__': arr =[ [ 1, 5 ], [12, 14]] Max = 1000005 N = len(arr) cntNumInRang(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program to implement
// the above approach
using System;
class GFG
{
public static int Max = 1000005;
// Function to check if a number is divisible
// by all of its non-zero digits or not
static bool CheckDivByAllDigits(int number)
{
// Stores the number
int n = number;
// Iterate over the digits
// of the numbers
while (n > 0) {
// If digit of number
// is non-zero
if (n % 10 != 0)
// If number is not divisible
// by its current digit
if (number % (n % 10) != 0)
{
return false;
}
// Update n
n /= 10;
}
return true;
}
// Function to count of numbers which are
// divisible by all of its non-zero
// digits in the range [1, i]
static void cntNumInRang(int[, ] arr, int N)
{
// Stores count of numbers which are
// divisible by all of its non-zero
// digits in the range [1, i]
int[] prefCntDiv = new int[Max + 1];
// Iterate over the range [1, Max]
for (int i = 1; i <= Max; i++) {
int ans = 0;
if (CheckDivByAllDigits(i))
ans = 1;
// Update
prefCntDiv[i] = prefCntDiv[i - 1] + ans;
}
// Traverse the array, arr[]
for (int i = 0; i < N; i++)
Console.Write((prefCntDiv[arr[i, 1]]
- prefCntDiv[arr[i, 0] - 1])
+ " ");
}
// Driver Code
public static void Main(string[] args)
{
int[, ] arr = { { 1, 5 }, { 12, 14 } };
int N = arr.GetLength(0);
cntNumInRang(arr, N);
}
}
// This code is contributed by chitranayal.
Javascript
<script>
// Javascript program to implement
// the above approach
const Max = 1000005;
// Function to check if a number is divisible
// by all of its non-zero digits or not
function CheckDivByAllDigits(number)
{
// Stores the number
let n = number;
// Iterate over the digits
// of the numbers
while (n > 0) {
// If digit of number
// is non-zero
if (n % 10)
// If number is not divisible
// by its current digit
if (number % (n % 10)) {
return false;
}
// Update n
n = parseInt(n / 10);
}
return true;
}
// Function to count of numbers which are
// divisible by all of its non-zero
// digits in the range [1, i]
function cntNumInRang(arr, N)
{
// Stores count of numbers which are
// divisible by all of its non-zero
// digits in the range [1, i]
let prefCntDiv = new Array(Max).fill(0);
// Iterate over the range [1, Max]
for (let i = 1; i <= Max; i++) {
// Update
prefCntDiv[i] = prefCntDiv[i - 1]
+ (CheckDivByAllDigits(i));
}
// Traverse the array, arr[]
for (let i = 0; i < N; i++)
document.write((prefCntDiv[arr[i][1]]
- prefCntDiv[arr[i][0] - 1])
+ " ");
}
// Driver Code
let arr = [ [ 1, 5 ], [ 12, 14 ] ];
let N = arr.length;
cntNumInRang(arr, N);
</script>
5 1
Complejidad de tiempo: O(N + Max), donde Max es el valor máximo de arr[i][1]
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por siddharth_25 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA