Dado un arreglo A[] con N enteros, para cada entero A[i] en el arreglo, la tarea es encontrar el número de enteros A[j] (j != i) en el arreglo tal que A[i] % A[j] = 0 o A[j] % A[i] = 0 .
Ejemplos:
Entrada: A = {2, 3, 4, 5, 6} Salida
: 2 1 1 0 2 Explicación: Para i=0, los índices válidos son 2 y 4 como 4%2 = 0 y 6%2 = 0. Para i=1, el único índice válido es 4 como 6%3 = 0. Para i=2, el único índice válido es 0 como 4%2 = 0. Para i=3, no hay índices válidos. Para i=0, los índices válidos son 0 y 1 como 6%2 = 0 y 6%3 = 0.Entrada: A = {6, 6, 6, 6, 6} Salida
: 4 4 4 4 4
Enfoque: El problema dado se puede resolver utilizando la observación de que el número de enteros que satisface la condición dada se puede clasificar en dos casos. Suponga que el número entero actual es P y Q es un número entero que satisface las condiciones dadas.
- Caso 1 donde Q es múltiplo de P . Por lo tanto, la cantidad de enteros en la array dada que son divisibles por P es la respuesta requerida. Este caso se puede manejar usando una simple modificación de la Criba de Eratóstenes que se discute aquí .
- Caso 2 donde P es múltiplo de Q . Por lo tanto, la cantidad de enteros en la array dada que Q divide a P es la respuesta requerida. Este caso se puede manejar de manera similar usando un tamiz como el del 1er Caso.
Entonces, la respuesta requerida para cualquier número entero es la suma de los números enteros resultantes del Caso 1 y el Caso 2 . En los casos en que P = Q , tanto el Caso 1 como el Caso 2 representan el mismo valor y deben considerarse solo una vez.
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 find the count of integers
// such that A[i]%A[j] = 0 or A[j]%A[i] = 0
// for each index of the array A[]
void countIndex(int A[], int N)
{
// Stores the maximum integer in A[]
int MAX = *max_element(A, A + N);
// Stores the frequency of each
// element in the array A[]
vector<int> freq(MAX + 1, 0);
for (int i = 0; i < N; i++)
freq[A[i]]++;
// Stores the valid integers in A[]
// for all integers from 1 to MAX
vector<int> res(MAX + 1, 0);
for (int i = 1; i <= MAX; ++i) {
for (int j = i; j <= MAX; j += i) {
// Case where P = Q
if (i == j) {
// Subtract 1 because P & Q
// cannot have same index
res[i] += (freq[j] - 1);
}
else {
// Case 1
res[i] += freq[j];
// Case 2
res[j] += freq[i];
}
}
}
// Loop to print answer for
// each index of array A[]
for (int i = 0; i < N; i++) {
cout << res[A[i]] << " ";
}
}
// Driver Code
int main()
{
int A[] = { 2, 3, 4, 5, 6 };
int N = sizeof(A) / sizeof(int);
// Function Call
countIndex(A, N);
return 0;
}
Java
// Java Program for the above approach
import java.util.*;
class GFG{
// Function to find the count of integers
// such that A[i]%A[j] = 0 or A[j]%A[i] = 0
// for each index of the array []A
static void countIndex(int []A, int N)
{
// Stores the maximum integer in []A
int MAX = Arrays.stream(A).max().getAsInt();
// Stores the frequency of each
// element in the array []A
int []freq = new int[MAX + 1];
for (int i = 0; i < N; i++)
freq[A[i]]++;
// Stores the valid integers in []A
// for all integers from 1 to MAX
int []res = new int[MAX + 1];
for (int i = 1; i <= MAX; ++i) {
for (int j = i; j <= MAX; j += i) {
// Case where P = Q
if (i == j) {
// Subtract 1 because P & Q
// cannot have same index
res[i] += (freq[j] - 1);
}
else {
// Case 1
res[i] += freq[j];
// Case 2
res[j] += freq[i];
}
}
}
// Loop to print answer for
// each index of array []A
for (int i = 0; i < N; i++) {
System.out.print(res[A[i]]+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
int []A = { 2, 3, 4, 5, 6 };
int N = A.length;
// Function Call
countIndex(A, N);
}
}
// This code is contributed by Princi Singh
Python3
# Python 3 Program for the above approach # Function to find the count of integers # such that A[i]%A[j] = 0 or A[j]%A[i] = 0 # for each index of the array A[] def countIndex(A, N): # Stores the maximum integer in A[] MAX = max(A) # Stores the frequency of each # element in the array A[] freq = [0 for i in range(MAX+1)] for i in range(N): if A[i] in freq: freq[A[i]] += 1 else: freq[A[i]] = 1 # Stores the valid integers in A[] # for all integers from 1 to MAX res = [0 for i in range(MAX+1)] for i in range(1, MAX + 1, 1): for j in range(i, MAX + 1, i): # Case where P = Q if (i == j): # Subtract 1 because P & Q # cannot have same index res[i] += (freq[j] - 1) else: # Case 1 res[i] += freq[j] # Case 2 res[j] += freq[i] # Loop to print answer for # each index of array A[] for i in range(N): print(res[A[i]],end = " ") # Driver Code if __name__ == '__main__': A = [2, 3, 4, 5, 6] N = len(A) # Function Call countIndex(A, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program of above approach
using System;
public class GFG {
static void countIndex(int[] A, int N)
{
// Stores the maximum integer in []A
int MAX = A[0];
for (int i = 1; i < N; i++) {
if (A[i] > MAX) {
MAX = A[i];
}
}
// Stores the frequency of each
// element in the array []A
int[] freq = new int[MAX + 1];
for (int i = 0; i < N; i++)
freq[A[i]]++;
// Stores the valid integers in []A
// for all integers from 1 to MAX
int[] res = new int[MAX + 1];
for (int i = 1; i <= MAX; ++i) {
for (int j = i; j <= MAX; j += i) {
// Case where P = Q
if (i == j) {
// Subtract 1 because P & Q
// cannot have same index
res[i] += (freq[j] - 1);
}
else {
// Case 1
res[i] += freq[j];
// Case 2
res[j] += freq[i];
}
}
}
// Loop to print answer for
// each index of array []A
for (int i = 0; i < N; i++) {
Console.Write(res[A[i]] + " ");
}
}
// Driver Code
static public void Main()
{
int[] A = { 2, 3, 4, 5, 6 };
int N = A.Length;
// Function Call
countIndex(A, N);
}
}
// This code is contributed by maddler.
Javascript
<script>
// JavaScript program for the above approach;
// Function to find the count of integers
// such that A[i]%A[j] = 0 or A[j]%A[i] = 0
// for each index of the array A[]
function max_element(A, N) {
let MAX = Number.MIN_VALUE;
for (let i = 0; i < A.length; i++) {
if (A[i] > MAX) {
MAX = A[i];
}
}
return MAX;
}
function countIndex(A, N) {
// Stores the maximum integer in A[]
let MAX = max_element(A, A + N);
// Stores the frequency of each
// element in the array A[]
let freq = new Array(MAX + 1).fill(0);
for (let i = 0; i < N; i++)
freq[A[i]]++;
// Stores the valid integers in A[]
// for all integers from 1 to MAX
let res = new Array(MAX + 1).fill(0);
for (let i = 1; i <= MAX; ++i) {
for (let j = i; j <= MAX; j += i) {
// Case where P = Q
if (i == j) {
// Subtract 1 because P & Q
// cannot have same index
res[i] += (freq[j] - 1);
}
else {
// Case 1
res[i] += freq[j];
// Case 2
res[j] += freq[i];
}
}
}
// Loop to print answer for
// each index of array A[]
for (let i = 0; i < N; i++) {
document.write(res[A[i]] + " ");
}
}
// Driver Code
let A = [2, 3, 4, 5, 6];
let N = A.length;
// Function Call
countIndex(A, N);
// This code is contributed by Potta Lokesh
</script>
Producción
2 1 1 0 2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(MAX) donde MAX representa el entero máximo en la array dada.
Publicación traducida automáticamente
Artículo escrito por srikar1812 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA