Dada una array arr[] que consta de consultas de la forma {L, R} , la tarea de cada consulta es contar los números en el rango [L, R] que se pueden expresar como la suma de sus dígitos elevados a la potencia de conteo de dígitos .
Ejemplos:
Entrada: arr[][] = {{8, 11}}
Salida: 2
Explicación:
Del rango dado [1, 9], los números que se pueden expresar como la suma de su dígito elevado a la potencia de conteo de dígitos son:
- 8: Suma de dígitos = 8, Conteo de dígitos = 1. Por lo tanto, 8 1 es igual al número dado.
- 9: Suma de dígitos = 9, Conteo de dígitos = 1. Por lo tanto, 9 1 es igual al número dado.
Por lo tanto, la cuenta de tales números del rango dado es 2.
Entrada: arr[][] = {{10, 100}, {1, 400}}
Salida: 0 11
Enfoque ingenuo: el enfoque más simple es iterar sobre el rango arr[i][0] a arr[i][1] para cada consulta e imprimir el recuento de dichos números.
Complejidad de tiempo: O(Q*(R – L)*log 10 R), donde R y L denotan los límites del rango más largo.
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar precomputando y almacenando todos los números, ya sea que se puedan expresar como la suma de su dígito elevado a la potencia de conteo de dígitos o no. Finalmente, imprima el conteo para cada consulta de manera eficiente.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar, digamos ans[] , para almacenar en ans[i], si i puede expresarse como la suma de su dígito elevado a la potencia de cuenta de dígitos .
- Itere sobre el rango [1, 10 6 ] y actualice la array ans[] en consecuencia.
- Convierta la array ans[] en una array de suma de prefijos .
- Recorra la array dada de consultas arr[] y para cada consulta {arr[i][0], arr[i][1]} , imprima el valor de (ans[arr[i][1]] – ans[arr [i][1] – 1]) como la cuenta de números resultante que se puede expresar como la suma de su dígito elevada a la potencia de la cuenta de dígitos.
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;
#define R 100005
int arr[R];
// Function to check if a number N can be
// expressed as sum of its digits raised
// to the power of the count of digits
bool canExpress(int N)
{
int temp = N;
// Stores the number of digits
int n = 0;
while (N != 0) {
N /= 10;
n++;
}
// Stores the resultant number
N = temp;
int sum = 0;
while (N != 0) {
sum += pow(N % 10, n);
N /= 10;
}
// Return true if both the
// numbers are same
return (sum == temp);
}
// Function to precompute and store
// for all numbers whether they can
// be expressed
void precompute()
{
// Mark all the index which
// are plus perfect number
for (int i = 1; i < R; i++) {
// If true, then update the
// value at this index
if (canExpress(i)) {
arr[i] = 1;
}
}
// Compute prefix sum of the array
for (int i = 1; i < R; i++) {
arr[i] += arr[i - 1];
}
}
// Function to count array elements that
// can be expressed as the sum of digits
// raised to the power of count of digits
void countNumbers(int queries[][2], int N)
{
// Precompute the results
precompute();
// Traverse the queries
for (int i = 0; i < N; i++) {
int L1 = queries[i][0];
int R1 = queries[i][1];
// Print the resultant count
cout << (arr[R1] - arr[L1 - 1])
<< ' ';
}
}
// Driver Code
int main()
{
int queries[][2] = {
{ 1, 400 },
{ 1, 9 }
};
int N = sizeof(queries)
/ sizeof(queries[0]);
countNumbers(queries, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
class GFG{
static int R = 100005;
static int[] arr = new int[R];
// Function to check if a number N can be
// expressed as sum of its digits raised
// to the power of the count of digits
public static boolean canExpress(int N)
{
int temp = N;
// Stores the number of digits
int n = 0;
while (N != 0)
{
N /= 10;
n++;
}
// Stores the resultant number
N = temp;
int sum = 0;
while (N != 0)
{
sum += ((int)Math.pow(N % 10, n));
N /= 10;
}
// Return true if both the
// numbers are same
if (sum == temp)
return true;
return false;
}
// Function to precompute and store
// for all numbers whether they can
// be expressed
public static void precompute()
{
// Mark all the index which
// are plus perfect number
for(int i = 1; i < R; i++)
{
// If true, then update the
// value at this index
if (canExpress(i))
{
arr[i] = 1;
}
}
// Compute prefix sum of the array
for(int i = 1; i < R; i++)
{
arr[i] += arr[i - 1];
}
}
// Function to count array elements that
// can be expressed as the sum of digits
// raised to the power of count of digits
public static void countNumbers(int[][] queries, int N)
{
// Precompute the results
precompute();
// Traverse the queries
for(int i = 0; i < N; i++)
{
int L1 = queries[i][0];
int R1 = queries[i][1];
// Print the resultant count
System.out.print((arr[R1] - arr[L1 - 1]) + " ");
}
}
// Driver Code
public static void main(String args[])
{
int[][] queries = { { 1, 400 }, { 1, 9 } };
int N = queries.length;
// Function call
countNumbers(queries, N);
}
}
// This code is contributed by zack_aayush
Python3
# Python 3 program for the above approach R = 100005 arr = [0 for i in range(R)] # Function to check if a number N can be # expressed as sum of its digits raised # to the power of the count of digits def canExpress(N): temp = N # Stores the number of digits n = 0 while (N != 0): N //= 10 n += 1 # Stores the resultant number N = temp sum = 0 while (N != 0): sum += pow(N % 10, n) N //= 10 # Return true if both the # numbers are same return (sum == temp) # Function to precompute and store # for all numbers whether they can # be expressed def precompute(): # Mark all the index which # are plus perfect number for i in range(1, R, 1): # If true, then update the # value at this index if(canExpress(i)): arr[i] = 1 # Compute prefix sum of the array for i in range(1,R,1): arr[i] += arr[i - 1] # Function to count array elements that # can be expressed as the sum of digits # raised to the power of count of digits def countNumbers(queries, N): # Precompute the results precompute() # Traverse the queries for i in range(N): L1 = queries[i][0] R1 = queries[i][1] # Print the resultant count print((arr[R1] - arr[L1 - 1]),end = " ") # Driver Code if __name__ == '__main__': queries = [[1, 400],[1, 9]] N = len(queries) countNumbers(queries, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
static int R = 100005;
static int[] arr = new int[R];
// Function to check if a number N can be
// expressed as sum of its digits raised
// to the power of the count of digits
public static bool canExpress(int N)
{
int temp = N;
// Stores the number of digits
int n = 0;
while (N != 0)
{
N /= 10;
n++;
}
// Stores the resultant number
N = temp;
int sum = 0;
while (N != 0)
{
sum += ((int)Math.Pow(N % 10, n));
N /= 10;
}
// Return true if both the
// numbers are same
if (sum == temp)
return true;
return false;
}
// Function to precompute and store
// for all numbers whether they can
// be expressed
public static void precompute()
{
// Mark all the index which
// are plus perfect number
for(int i = 1; i < R; i++)
{
// If true, then update the
// value at this index
if (canExpress(i))
{
arr[i] = 1;
}
}
// Compute prefix sum of the array
for(int i = 1; i < R; i++)
{
arr[i] += arr[i - 1];
}
}
// Function to count array elements that
// can be expressed as the sum of digits
// raised to the power of count of digits
public static void countNumbers(int[,] queries, int N)
{
// Precompute the results
precompute();
// Traverse the queries
for(int i = 0; i < N; i++)
{
int L1 = queries[i, 0];
int R1 = queries[i, 1];
// Print the resultant count
Console.Write((arr[R1] - arr[L1 - 1]) + " ");
}
}
// Driver Code
static public void Main()
{
int[,] queries = { { 1, 400 }, { 1, 9 } };
int N = queries.GetLength(0);
// Function call
countNumbers(queries, N);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// javascript program for the above approach
var R = 100005;
var arr = Array(R).fill(0);
// Function to check if a number N can be
// expressed as sum of its digits raised
// to the power of the count of digits
function canExpress(N) {
var temp = N;
// Stores the number of digits
var n = 0;
while (N != 0) {
N = parseInt(N/10);
n++;
}
// Stores the resultant number
N = temp;
var sum = 0;
while (N != 0) {
sum += Math.pow(N % 10, n);
N = parseInt(N/10);
}
// Return true if both the
// numbers are same
return (sum == temp);
}
// Function to precompute and store
// for all numbers whether they can
// be expressed
function precompute() {
// Mark all the index which
// are plus perfect number
for (var i = 1; i < R; i++) {
// If true, then update the
// value at this index
if (canExpress(i)) {
arr[i] = 1;
}
}
// Compute prefix sum of the array
for (var i = 1; i < R; i++) {
arr[i] += arr[i - 1];
}
}
// Function to count array elements that
// can be expressed as the sum of digits
// raised to the power of count of digits
function countNumbers(queries , N) {
// Precompute the results
precompute();
// Traverse the queries
for (var i = 0; i < N; i++) {
var L1 = queries[i][0];
var R1 = queries[i][1];
// Print the resultant count
document.write((arr[R1] - arr[L1 - 1]) + " ");
}
}
// Driver Code
var queries = [ [ 1, 400 ], [ 1, 9 ] ];
var N = queries.length;
// function call
countNumbers(queries, N);
// This code is contributed by Princi Singh
</script>
Producción:
12 9
Complejidad de Tiempo: O(Q + 10 6 )
Espacio Auxiliar: O(10 6 )
Publicación traducida automáticamente
Artículo escrito por patelajeet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA