Dada una array Q[][] que consta de N consultas de la forma {L, R} , la tarea de cada consulta es encontrar el recuento total de los números del rango [L, R] que son divisibles por la suma de sus dígitos.
Ejemplos:
Entrada: Q[][]= {{5, 9}, {5, 20}}
Salida:
5
9
Explicación:
Consulta 1: Los números en el rango [5, 9] que son divisibles por la suma de sus dígitos son {5, 6, 7, 8, 9}.
Consulta 2: Los números en el rango [5, 20] que son divisibles por la suma de sus dígitos son { 5, 6, 7, 8, 9, 10, 12, 18, 20}.Entrada: Q[][] = {{1, 30}, {13, 15}}
Salida:
17
0
Explicación:
Consulta 1: Los números en el rango [5, 9] que son divisibles por la suma de sus dígitos son { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 18, 20, 21, 24, 27, 30}.
Consulta 2: No existe tal número en el rango [13, 15].
Enfoque: El problema se puede resolver utilizando el principio de inclusión-exclusión y la técnica de array de suma de prefijos .
Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array arr[] para almacenar en cada i- ésimo índice, el recuento de números hasta i que son divisibles por la suma de sus dígitos.
- Itere sobre el rango [1, 10 5 ] usando una variable, digamos i , y para cada i- ésimo elemento, verifique si i es divisible por la suma de sus dígitos.
- Si se determina que es cierto, establezca arr[i] = 1 .
- De lo contrario, establezca arr[i] = 0 .
- Modifique la array arr[] a su prefijo sum array .
- Recorra la array Q[][] y, para cada consulta, calcule el recuento total de los números requeridos del rango [L, R] , que es igual a arr[R] – arr[L – 1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the
// above approach
#include <bits/stdc++.h>
using namespace std;
int arr[100005];
// Function to check if the number x
// is divisible by its sum of digits
bool isDivisible(int x)
{
// Stores sum of digits of x
int sum = 0;
// Temporarily store x
int temp = x;
// Calculate sum
// of digits of x
while (x != 0) {
sum += x % 10;
x /= 10;
}
// If x is not divisible by sum
if (temp % sum)
return false;
// Otherwise
else
return true;
}
// Function to perform
// the precomputation
void precompute()
{
// Iterate from i equals 1 to 1e5
for (int i = 1; i <= 100000; i++) {
// Check if i is divisible
// by sum of its digits
if (isDivisible(i))
arr[i] = 1;
else
arr[i] = 0;
}
// Convert arr[] to prefix sum array
for (int i = 1; i <= 100000; i++) {
arr[i] = arr[i] + arr[i - 1];
}
}
// Driver code
int main()
{
// Given queries
vector<pair<int, int> > Q = { { 5, 9 }, { 5, 20 } };
precompute();
for (auto it : Q) {
// Using inclusion-exclusion
// principle, calculate the result
cout << arr[it.second] - arr[it.first - 1] << "\n";
}
return 0;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
static int arr[] = new int[100005];
// Function to check if the number x
// is divisible by its sum of digits
static boolean isDivisible(int x)
{
// Stores sum of digits of x
int sum = 0;
// Temporarily store x
int temp = x;
// Calculate sum
// of digits of x
while (x != 0) {
sum += x % 10;
x /= 10;
}
// If x is not divisible by sum
if (temp % sum != 0)
return false;
// Otherwise
else
return true;
}
// Function to perform
// the precomputation
static void precompute()
{
// Iterate from i equals 1 to 1e5
for (int i = 1; i <= 100000; i++) {
// Check if i is divisible
// by sum of its digits
if (isDivisible(i))
arr[i] = 1;
else
arr[i] = 0;
}
// Convert arr[] to prefix sum array
for (int i = 1; i <= 100000; i++) {
arr[i] = arr[i] + arr[i - 1];
}
}
// Driver Code
public static void main(String[] args)
{
// Given queries
int Q[][] = { { 5, 9 }, { 5, 20 } };
precompute();
for (int q[] : Q) {
// Using inclusion-exclusion
// principle, calculate the result
System.out.println(arr[q[1]] - arr[q[0] - 1]);
}
}
}
Python3
# Python program for the above approach arr = [0] * 100005 # Function to check if the number x # is divisible by its sum of digits def isDivisible(x): # Stores sum of digits of x sum = 0; # Temporarily store x temp = x; # Calculate sum # of digits of x while (x != 0): sum += x % 10; x = x // 10; # If x is not divisible by sum if (temp % sum != 0): return False; # Otherwise else: return True; # Function to perform # the precomputation def precompute(): # Iterate from i equals 1 to 1e5 for i in range(1, 100000 + 1): # Check if i is divisible # by sum of its digits if (isDivisible(i)): arr[i] = 1; else: arr[i] = 0; # Convert arr[] to prefix sum array for i in range(1, 100000 + 1): arr[i] = arr[i] + arr[i - 1]; # Driver Code # Given queries Q = [[5, 9], [5, 20]]; precompute(); for q in Q: # Using inclusion-exclusion # principle, calculate the result print(arr[q[1]] - arr[q[0] - 1]); # This code is contributed by saurabh_jaiswal.
C#
// C# program for the above approach
using System;
class GFG{
static int []arr = new int[100005];
// Function to check if the number x
// is divisible by its sum of digits
static bool isDivisible(int x)
{
// Stores sum of digits of x
int sum = 0;
// Temporarily store x
int temp = x;
// Calculate sum
// of digits of x
while (x != 0)
{
sum += x % 10;
x /= 10;
}
// If x is not divisible by sum
if (temp % sum != 0)
return false;
// Otherwise
else
return true;
}
// Function to perform
// the precomputation
static void precompute()
{
// Iterate from i equals 1 to 1e5
for(int i = 1; i <= 100000; i++)
{
// Check if i is divisible
// by sum of its digits
if (isDivisible(i))
arr[i] = 1;
else
arr[i] = 0;
}
// Convert []arr to prefix sum array
for(int i = 1; i <= 100000; i++)
{
arr[i] = arr[i] + arr[i - 1];
}
}
public static int[] GetRow(int[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for(var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver Code
public static void Main(String[] args)
{
// Given queries
int [,]Q = { { 5, 9 }, { 5, 20 } };
int []q;
precompute();
for(int i = 0; i < Q.GetLength(0); i++)
{
q = GetRow(Q,i);
// Using inclusion-exclusion
// principle, calculate the result
Console.WriteLine(arr[q[1]] - arr[q[0] - 1]);
}
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
let arr = new Array(100005).fill(0);
// Function to check if the number x
// is divisible by its sum of digits
function isDivisible(x) {
// Stores sum of digits of x
let sum = 0;
// Temporarily store x
let temp = x;
// Calculate sum
// of digits of x
while (x != 0) {
sum += x % 10;
x = Math.floor(x / 10);
}
// If x is not divisible by sum
if (temp % sum != 0)
return false;
// Otherwise
else
return true;
}
// Function to perform
// the precomputation
function precompute() {
// Iterate from i equals 1 to 1e5
for (let i = 1; i <= 100000; i++) {
// Check if i is divisible
// by sum of its digits
if (isDivisible(i))
arr[i] = 1;
else
arr[i] = 0;
}
// Convert arr[] to prefix sum array
for (let i = 1; i <= 100000; i++) {
arr[i] = arr[i] + arr[i - 1];
}
}
// Driver Code
// Given queries
let Q = [[5, 9], [5, 20]];
precompute();
for (let q of Q)
{
// Using inclusion-exclusion
// principle, calculate the result
document.write(arr[q[1]] - arr[q[0] - 1] + " <br>");
}
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
5 9
Complejidad de tiempo: O(N)
Espacio auxiliar: O(maxm), donde maxm denota el valor máximo de R.
Publicación traducida automáticamente
Artículo escrito por patelajeet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA