Dado un arreglo, cuente los pares en el arreglo de modo que un elemento del par divida al otro.
Ejemplos:
Input : arr[] = {1, 2, 3}
Output : 2
The two pairs are (1, 2) and (1, 3)
Input : arr[] = {2, 3, 5, 7}
Output: 0
Enfoque ingenuo: el enfoque de fuerza bruta se puede implementar iterando a través de cada elemento de la array y verificando dónde tenemos pares (i,j) de modo que arr[i]%arr[j]=0.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to count divisible pairs.
#include <bits/stdc++.h>
using namespace std;
int countDivisibles(int arr[], int n)
{
int res = 0;
// Iterate through all pairs
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
// Increment count if one divides
// other
if (arr[i] % arr[j] == 0 ||
arr[j] % arr[i] == 0)
res++;
return res;
}
int main()
{
int a[] = {1, 2, 3, 9};
int n = sizeof(a) / sizeof(a[0]);
cout << countDivisibles(a, n);
return 0;
}
Java
// Java program to count
// divisible pairs.
class GFG {
// Function returns count
// of divisible pairs
static int countDivisibles(int arr[],
int n)
{
int res = 0;
// Iterate through all pairs
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
// Increment count if
// one divides other
if (arr[i] % arr[j] == 0 ||
arr[j] % arr[i] == 0)
res++;
return res;
}
// Driver Code
public static void main(String[] args)
{
int a[] = new int[]{1, 2, 3, 9};
int n = a.length;
System.out.print(countDivisibles(a, n));
}
}
// This code is contributed by Smitha.
Python3
# Python3 program to count # divisible pairs. def countDivisibles(arr, n) : res = 0 # Iterate through all pairs for i in range(0, n) : for j in range(i+1, n) : # Increment count if one divides # other if (arr[i] % arr[j] == 0 or arr[j] % arr[i] == 0) : res+=1 return res # Driver code if __name__=='__main__': a = [1, 2, 3, 9] n = len(a) print(countDivisibles(a, n) ) # this code is contributed by # Smitha Dinesh Semwal
C#
// Java program to count
// divisible pairs.
using System;
class GFG {
// Function returns count
// of divisible pairs
static int countDivisibles(int []arr,
int n)
{
int res = 0;
// Iterate through all pairs
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
// Increment count if
// one divides other
if (arr[i] % arr[j] == 0 ||
arr[j] % arr[i] == 0)
res++;
return res;
}
// Driver Code
public static void Main(String[] args)
{
int[] a = new int[4] {1, 2, 3, 9};
int n = a.Length;
Console.Write(countDivisibles(a, n));
}
}
// This code is contributed by Smitha.
PHP
<?php
// PHP program to count divisible pairs.
function countDivisibles($arr, $n)
{
$res = 0;
// Iterate through all pairs
for ($i = 0; $i < $n; $i++)
for ($j = $i + 1; $j < $n; $j++)
// Increment count if one divides
// other
if ($arr[$i] % $arr[$j] == 0 ||
$arr[$j] % $arr[$i] == 0)
$res++;
return $res;
}
$a = array(1, 2, 3, 9);
$n = count($a);
echo (countDivisibles($a, $n));
?>
Javascript
<script>
// JavaScript program to count divisible pairs.
function countDivisibles(arr, n) {
let res = 0;
// Iterate through all pairs
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
// Increment count if one divides
// other
if (arr[i] % arr[j] == 0 ||
arr[j] % arr[i] == 0)
res++;
return res;
}
let a = [1, 2, 3, 9];
let n = a.length;
document.write(countDivisibles(a, n));
</script>
Producción
4
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver de manera eficiente contando los factores totales del elemento presente en la array. Como arr[i]%arr[j]==0 indica que arr[j] es un divisor/factor de arr[i] . Entonces, para cada elemento, contamos el número total de sus factores presentes en la array usando un mapa desordenado .
Este enfoque se puede implementar en los siguientes pasos.
i) Almacenar la frecuencia de todos los números presentes en la array. Esto se puede almacenar en el mapa desordenado para que podamos acceder a la frecuencia de cualquier elemento en la complejidad de tiempo O(1) .
ii) Para cada elemento de la array indicado como arr[i], encuentre todos los factores de ese elemento en complejidad temporal O(sqrt(n)) .
iii) Y para todos los factores, cuente cuántas veces ese factor (denotemos como f) ocurrió en la array, ya que muchas veces arr[i]%f será 0.
iv) Devolver el recuento total de dichos pares ordenados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the total
// count of pairs such that
// arr[i]%arr[j]==0
int total_count(int arr[], int n)
{
int count = 0;
// Storing the occurrence of
// every element in array in
// unordered_map
unordered_map<int, int> freq;
for(int i=0;i<n;i++)
{
freq[arr[i]]++;
}
// Iterating through every element
// and finding all the divisors of
// that element and then checking
// how many of them are present
// in array arr[]
for(int i=0;i<n;i++)
{
for (int j=1;j<=sqrt(arr[i]);j++)
{
if(arr[i]%j==0)
{
if(arr[i]==j*j)
{ // If divisors are equal,
// then take only one as
// it will be perfect square
// root of arr[i]
count+=freq[j];
}
else
{
// Else take both j and arr[i]/j
// as both will be divisors
count+=freq[j]+ freq[arr[i]/j];
}
}
}
// As all the elements is divisible
// by itself and is counted in freq[]
// so reducing its count
count=count-1;
}
// Returning final count
return count;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
cout<<total_count(arr,N);
return 0;
}
// This code is contributed by Pushpesh Raj
Java
// Java program to count
// divisible pairs.
import java.util.*;
public class GFG {
// Function to return the total
// count of pairs such that
// arr[i]%arr[j]==0
public static int total_count(int[] arr, int n)
{
int count = 0;
// Storing the occurrence of
// every element in array in
// unordered_map
HashMap<Integer, Integer> freq
= new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
if (!freq.containsKey(arr[i])) {
freq.put(arr[i], 1);
}
else {
freq.put(arr[i], freq.get(arr[i]) + 1);
}
}
// Iterating through every element
// and finding all the divisors of
// that element and then checking
// how many of them are present
// in array arr[]
for (int i = 0; i < n; i++) {
for (int j = 1; j <= Math.sqrt(arr[i]); j++) {
if (arr[i] % j == 0) {
if (arr[i] == j * j) { // If divisors
// are equal,
// then take only one as
// it will be perfect square
// root of arr[i]
count += freq.get(j);
}
else {
// Else take both j and arr[i]/j
// as both will be divisors
count += freq.get(j)
+ freq.get(arr[i] / j);
}
}
}
// As all the elements is divisible
// by itself and is counted in freq[]
// so reducing its count
count = count - 1;
}
// Returning final count
return count;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 9 };
int N = arr.length;
System.out.print(total_count(arr, N));
}
// This code is contributed by Aarti_Rathi
}
Python3
# Python program to count divisible pairs.
import math
# Function to return the total count of pairs such
# that arr[i]%arr[j]==0
def total_count(arr, N):
count = 0
# Storing the occurance of every element in array
# in dictionary
freq = {}
for i in range(0, N):
if arr[i] not in freq:
freq[arr[i]] = 1
else:
freq[arr[i]] += 1
# Iterating through every element and finding all the
# divisors of that element and then checking how many
# of them are present in array arr[]
for i in range(0, N):
for j in range(1, int(math.sqrt(arr[i]))+1):
if arr[i] % j == 0:
if arr[i] == j*j:
# If divisors are equal, then take only
# one as it will be perfect square root
# of arr[i]
count += freq[j]
else:
# Else take both j and arr[i]/j as both
# will be divisors
count += freq[j]+freq[arr[i]/j]
# As all the elements is divisible by itself and
# is counted in freq[] so reducing its count
count = count-1
# returning final count
return count
arr = [1, 2, 3, 9]
N = len(arr)
print(total_count(arr, N))
# This code is contributed by lokesh (lokeshmvs21).
C#
// C# program to count
// divisible pairs.
using System;
using System.Collections.Generic;
public class GFG {
// Function to return the total
// count of pairs such that
// arr[i]%arr[j]==0
public static int total_count(int[] arr, int n)
{
int count = 0;
// Storing the occurrence of
// every element in array in
// unordered_map
Dictionary<int, int> freq
= new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
if (!freq.ContainsKey(arr[i])) {
freq[arr[i]] = 1;
}
else {
freq[arr[i]] += 1;
}
}
// Iterating through every element
// and finding all the divisors of
// that element and then checking
// how many of them are present
// in array arr[]
for (int i = 0; i < n; i++) {
for (int j = 1; j <= Math.Sqrt(arr[i]); j++) {
if (arr[i] % j == 0) {
if (arr[i] == j * j) { // If divisors
// are equal,
// then take only one as
// it will be perfect square
// root of arr[i]
count += freq[j];
}
else {
// Else take both j and arr[i]/j
// as both will be divisors
count += freq[j] + freq[arr[i] / j];
}
}
}
// As all the elements is divisible
// by itself and is counted in freq[]
// so reducing its count
count = count - 1;
}
// Returning final count
return count;
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 9 };
int N = arr.Length;
Console.Write(total_count(arr, N));
}
}
// This code is contributed by phasing17
Producción
4
Complejidad temporal: O(n 3/2 )
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por vidyabhushan singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA