Dado un arreglo arr[] que consta de N elementos y Q consultas representadas por L y R que denotan un rango, la tarea es imprimir la cantidad de números de Armstrong en el subarreglo [L, R] .
Ejemplos:
Entrada: arr[] = {18, 153, 8, 9, 14, 5}
Consulta 1: consulta (L=0, R=5)
Consulta 2: consulta (L=3, R=5)
Salida: 4
2
Explicación :
18 => 1*1 + 8*8 != 18
153 => 1*1*1 + 5*5*5 + 3*3*3 = 153
8 => 8 = 8
9 => 9 = 9
14 = > 1*1 + 4*4 != 14
Consulta 1: El subarreglo[0…5] tiene 4 números de Armstrong a saber. {153, 8, 9, 5}
Consulta 2: El subarreglo [3…5] tiene 2 números de Armstrong, a saber. {9, 5}
Enfoque:
la idea es usar el algoritmo de MO para preprocesar todas las consultas de modo que el resultado de una consulta se pueda usar en la siguiente consulta.
- Ordene todas las consultas de manera que las consultas con valores L de 0 a √n – 1 se junten, seguidas de las consultas de √n a 2 ×√n – 1 , y así sucesivamente. Todas las consultas dentro de un bloque se clasifican en orden creciente de valores R.
- Procese todas las consultas una por una y aumente el conteo de números de Armstrong y almacene el resultado en la estructura.
- Deje que ‘ count_Armstrong ‘ almacene el recuento de números de Armstrong en la consulta anterior.
- Elimine elementos adicionales de la consulta anterior y agregue nuevos elementos para la consulta actual. Por ejemplo, si la consulta anterior fue [0, 8] y la consulta actual es [3, 9], elimine los elementos arr[0], arr[1] y arr[2] y agregue arr[9].
- Para mostrar los resultados, ordene las consultas en el orden en que se proporcionaron.
Agregar elementos
- Si el elemento actual es un número de Armstrong, incremente count_Armstrong .
Quitar elementos
- Si el elemento actual es un número de Armstrong, disminuya count_Armstrong .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count the
// number of Armstrong numbers
// in subarray using MO’s algorithm
#include <bits/stdc++.h>
using namespace std;
// Variable to represent block size.
// This is made global so compare()
// of sort can use it.
int block;
// Structure to represent
// a query range
struct Query {
int L, R, index;
// Count of Armstrong
// numbers
int armstrong;
};
// To store the count of
// Armstrong numbers
int count_Armstrong;
// Function used to sort all queries so that
// all queries of the same block are arranged
// together and within a block, queries are
// sorted in increasing order of R values.
bool compare(Query x, Query y)
{
// Different blocks, sort by block.
if (x.L / block != y.L / block)
return x.L / block < y.L / block;
// Same block, sort by R value
return x.R < y.R;
}
// Function used to sort all
// queries in order of their
// index value so that results
// of queries can be printed
// in same order as of input
bool compare1(Query x, Query y)
{
return x.index < y.index;
}
// Function that return true
// if num is armstrong
// else return false
bool isArmstrong(int x)
{
int n = to_string(x).size();
int sum1 = 0;
int temp = x;
while (temp > 0) {
int digit = temp % 10;
sum1 += pow(digit, n);
temp /= 10;
}
if (sum1 == x)
return true;
return false;
}
// Function to Add elements
// of current range
void add(int currL, int a[])
{
// If a[currL] is a Armstrong number
// then increment count_Armstrong
if (isArmstrong(a[currL]))
count_Armstrong++;
}
// Function to remove elements
// of previous range
void remove(int currR, int a[])
{
// If a[currL] is a Armstrong number
// then decrement count_Armstrong
if (isArmstrong(a[currR]))
count_Armstrong--;
}
// Function to generate the result of queries
void queryResults(int a[], int n, Query q[],
int m)
{
// Initialize count_Armstrong to 0
count_Armstrong = 0;
// Find block size
block = (int)sqrt(n);
// Sort all queries so that queries of
// same blocks are arranged together.
sort(q, q + m, compare);
// Initialize current L, current R and
// current result
int currL = 0, currR = 0;
for (int i = 0; i < m; i++) {
// L and R values of current range
int L = q[i].L, R = q[i].R;
// Add Elements of current range
while (currR <= R) {
add(currR, a);
currR++;
}
while (currL > L) {
add(currL - 1, a);
currL--;
}
// Remove element of previous range
while (currR > R + 1)
{
remove(currR - 1, a);
currR--;
}
while (currL < L) {
remove(currL, a);
currL++;
}
q[i].armstrong = count_Armstrong;
}
}
// Function to display the results of
// queries in their initial order
void printResults(Query q[], int m)
{
sort(q, q + m, compare1);
for (int i = 0; i < m; i++) {
cout << q[i].armstrong << endl;
}
}
// Driver Code
int main()
{
int arr[] = { 18, 153, 8, 9, 14, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
Query q[] = { { 0, 5, 0, 0 },
{ 3, 5, 1, 0 } };
int m = sizeof(q) / sizeof(q[0]);
queryResults(arr, n, q, m);
printResults(q, m);
return 0;
}
Java
// Java implementation to count the
// number of Armstrong numbers
// in subarray using MO’s algorithm
import java.io.*;
import java.util.*;
// Class to represent
// a query range
class Query
{
int L, R, index;
// Count of Armstrong
// numbers
int armstrong;
Query(int L, int R, int index,
int armstrong)
{
this.L = L;
this.R = R;
this.index = index;
this.armstrong = armstrong;
}
}
class GFG{
// Variable to represent block size.
static int block;
// To store the count of
// Armstrong numbers
static int count_Armstrong;
// Function that return true
// if num is armstrong
// else return false
static boolean isArmstrong(int x)
{
int n = String.valueOf(x).length();
int sum1 = 0;
int temp = x;
while (temp > 0)
{
int digit = temp % 10;
sum1 += Math.pow(digit, n);
temp /= 10;
}
if (sum1 == x)
return true;
return false;
}
// Function to Add elements
// of current range
static void add(int currL, int a[])
{
// If a[currL] is a Armstrong number
// then increment count_Armstrong
if (isArmstrong(a[currL]))
count_Armstrong++;
}
// Function to remove elements
// of previous range
static void remove(int currR, int a[])
{
// If a[currL] is a Armstrong number
// then decrement count_Armstrong
if (isArmstrong(a[currR]))
count_Armstrong--;
}
// Function to generate the result of queries
static void queryResults(int a[], int n, Query q[],
int m)
{
// Initialize count_Armstrong to 0
count_Armstrong = 0;
// Find block size
block = (int)(Math.sqrt(n));
// sort all queries so that
// all queries of the same block are arranged
// together and within a block, queries are
// sorted in increasing order of R values.
Arrays.sort(q, (Query x, Query y) ->
{
// Different blocks, sort by block.
if (x.L / block != y.L / block)
return x.L / block - y.L / block;
// Same block, sort by R value
return x.R - y.R;
});
// Initialize current L, current R and
// current result
int currL = 0, currR = 0;
for(int i = 0; i < m; i++)
{
// L and R values of current range
int L = q[i].L, R = q[i].R;
// Add Elements of current range
while (currR <= R)
{
add(currR, a);
currR++;
}
while (currL > L)
{
add(currL - 1, a);
currL--;
}
// Remove element of previous range
while (currR > R + 1)
{
remove(currR - 1, a);
currR--;
}
while (currL < L)
{
remove(currL, a);
currL++;
}
q[i].armstrong = count_Armstrong;
}
}
// Function to display the results of
// queries in their initial order
static void printResults(Query q[], int m)
{
Arrays.sort(q, (Query x, Query y) ->
// sort all queries
// in order of their
// index value so that results
// of queries can be printed
// in same order as of input);
x.index - y.index);
for(int i = 0; i < m; i++)
{
System.out.println(q[i].armstrong);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 18, 153, 8, 9, 14, 5 };
int n = arr.length;
Query q[] = new Query[2];
q[0] = new Query(0, 5, 0, 0);
q[1] = new Query(3, 5, 1, 0);
int m = q.length;
queryResults(arr, n, q, m);
printResults(q, m);
}
}
// This code is contributed by jithin
Producción:
4 2
Complejidad de tiempo: O(Q * √N)
Artículo relacionado: Consultas de rango para la cantidad de números de Armstrong en una array con actualizaciones
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA