Dada una array arr[] de N enteros positivos. Para todos los pares posibles (x, y) la tarea es encontrar la sumatoria de x/y .
Nota: si la parte decimal de (x/y) es &ge 0.5, agregue el techo de (x/y) , de lo contrario, agregue el piso de (x/y) .
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 12
Explicación:
Todos los pares posibles con división son:
(1/1) = 1, (1/2) = 1, (1/3) = 0
(2 /1) = 2, (2/2) = 1, (2/3) = 1
(3/1) = 3, (3/2) = 2, (3/3) = 1
Suma = 1 + 1 + 0 + 2 + 1 + 1 + 3 + 2 + 1 = 12.
Entrada: arr[] = {1, 2, 3, 4}
Salida: 22
Explicación:
Todos los pares posibles con división son:
(1/1) = 1 , (1/2) = 1, (1/3) = 0, (1/4) = 0
(2/1) = 2, (2/2) = 1, (2/3) = 1, (2 /4) = 1
(3/1) = 3, (3/2) = 2, (3/3) = 1, (3/4) = 1
(4/1) = 4, (4/2) = 2, (4/3) = 1, (4/4) = 1
Suma = 1 + 1 + 0 + 0 + 2 + 1 + 1 + 1 + 3 + 2 + 1 + 1 + 4 + 2 + 1 + 1 = 22.
Enfoque ingenuo: la idea es generar todos los pares posibles en la array dada y encontrar la suma de (x/y) para cada par (x, y) .
Complejidad de tiempo: O(N 2 )
Enfoque eficiente:
Para optimizar el método anterior, tenemos que calcular la array de frecuencias donde freq[i] denota el número de ocurrencias del número i.
- Para cualquier número X dado, todos los números que van desde [0.5X, 1.5X] contribuirían con 1 a la respuesta cuando se dividen por X. De manera similar, todos los números que van desde [1.5X, 2.5X] contribuirían con 2 a la respuesta cuando se divide por X.
- Generalizando este hecho, todos los números que van desde [(n-0.5)X, (n+0.5)X] contribuirían con n a la respuesta cuando se divide por X.
- Por lo tanto, para cada número P en el rango de 1 a N, podemos obtener el recuento de los números que se encuentran en el rango dado [L, R] simplemente calculando una suma de prefijos de la array de frecuencias.
- Para un número P, necesitamos consultar los rangos en la mayoría de los tiempos N/P.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to compute the
// sum of division of all the possible
// pairs for the given array
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to compute the sum
int func(int arr[], int n)
{
double ans = 0;
int maxx = 0;
double freq[100005] = { 0 };
int temp;
// counting frequency
// of each term
// and finding maximum
// among it
for (int i = 0; i < n; i++) {
temp = arr[i];
freq[temp]++;
maxx = max(maxx, temp);
}
// Making cumulative frequency
for (int i = 1; i <= maxx; i++) {
freq[i] += freq[i - 1];
}
for (int i = 1; i <= maxx; i++) {
if (freq[i]) {
i = (double)i;
double j;
ll value = 0;
// Taking the ceil value
double cur = ceil(0.5 * i) - 1.0;
for (j = 1.5;; j++) {
int val = min(maxx, (int)(ceil(i * j) - 1.0));
int times = (freq[i] - freq[i - 1]), con = j - 0.5;
// nos. in [(n-0.5)X, (n+0.5)X)
// range will add n to the ans
ans += times * con * (freq[(int)val] - freq[(int)cur]);
cur = val;
if (val == maxx)
break;
}
}
}
// Return the final result
return (ll)ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << func(arr, n) << endl;
return 0;
}
Java
// Java implementation to compute the
// sum of division of all the possible
// pairs for the given array
class GFG{
// Function to compute the sum
static long func(int arr[], int n)
{
double ans = 0;
int maxx = 0;
double freq[] = new double[100005];
int temp;
// Counting frequency of each term
// and finding maximum among it
for(int i = 0; i < n; i++)
{
temp = arr[i];
freq[temp]++;
maxx = Math.max(maxx, temp);
}
// Making cumulative frequency
for(int i = 1; i <= maxx; i++)
{
freq[i] += freq[i - 1];
}
for(int i = 1; i <= maxx; i++)
{
if (freq[i] != 0)
{
double j;
// Taking the ceil value
double cur = Math.ceil(0.5 * i) - 1.0;
for(j = 1.5;; j++)
{
int val = Math.min(maxx,
(int)(Math.ceil(i * j) - 1.0));
int times = (int)(freq[i] -
freq[i - 1]),
con = (int)(j - 0.5);
// nos. in [(n-0.5)X, (n+0.5)X)
// range will add n to the ans
ans += times * con * (freq[(int)val] -
freq[(int)cur]);
cur = val;
if (val == maxx)
break;
}
}
}
// Return the final result
return (long)ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3 };
int n = arr.length;
System.out.print(func(arr, n) + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to compute the sum # of division of all the possible # pairs for the given array from math import * # Function to compute the sum def func (arr, n): ans = 0 maxx = 0 freq = [0] * 100005 temp = 0 # Counting frequency of each term # and finding maximum among it for i in range(n): temp = arr[i] freq[temp] += 1 maxx = max(maxx, temp) # Making cumulative frequency for i in range(1, maxx + 1): freq[i] += freq[i - 1] for i in range(1, maxx + 1): if (freq[i]): value = 0 # Taking the ceil value cur = ceil(0.5 * i) - 1.0 j = 1.5 while (1): val = min(maxx, (ceil(i * j) - 1.0)) times = (freq[i] - freq[i - 1]) con = j - 0.5 # nos. in [(n-0.5)X , (n+0.5)X) # range will add n to the ans ans += times * con * (freq[int(val)] - freq[int(cur)]) cur = val if (val == maxx): break j += 1 return int(ans) # Driver code if __name__ == '__main__': arr = [ 1, 2, 3 ] n = len(arr) print(func(arr, n)) # This code is contributed by himanshu77
C#
// C# implementation to compute the
// sum of division of all the possible
// pairs for the given array
using System;
class GFG{
// Function to compute the sum
static long func(int []arr, int n)
{
double ans = 0;
int maxx = 0;
double []freq = new double[100005];
int temp;
// Counting frequency of each term
// and finding maximum among it
for(int i = 0; i < n; i++)
{
temp = arr[i];
freq[temp]++;
maxx = Math.Max(maxx, temp);
}
// Making cumulative frequency
for(int i = 1; i <= maxx; i++)
{
freq[i] += freq[i - 1];
}
for(int i = 1; i <= maxx; i++)
{
if (freq[i] != 0)
{
double j;
// Taking the ceil value
double cur = Math.Ceiling(0.5 * i) - 1.0;
for(j = 1.5;; j++)
{
int val = Math.Min(maxx,
(int)(Math.Ceiling(i * j) - 1.0));
int times = (int)(freq[i] -
freq[i - 1]),
con = (int)(j - 0.5);
// nos. in [(n-0.5)X, (n+0.5)X)
// range will add n to the ans
ans += times * con * (freq[(int)val] -
freq[(int)cur]);
cur = val;
if (val == maxx)
break;
}
}
}
// Return the readonly result
return (long)ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3 };
int n = arr.Length;
Console.Write(func(arr, n) + "\n");
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript implementation to compute the
// sum of division of all the possible
// pairs for the given array
// Function to compute the sum
function func(arr, n)
{
let ans = 0;
let maxx = 0;
let freq = Array.from({length: 100005}, (_, i) => 0);
let temp;
// Counting frequency of each term
// and finding maximum among it
for(let i = 0; i < n; i++)
{
temp = arr[i];
freq[temp]++;
maxx = Math.max(maxx, temp);
}
// Making cumulative frequency
for(let i = 1; i <= maxx; i++)
{
freq[i] += freq[i - 1];
}
for(let i = 1; i <= maxx; i++)
{
if (freq[i] != 0)
{
let j;
// Taking the ceil value
let cur = Math.ceil(0.5 * i) - 1.0;
for(j = 1.5;; j++)
{
let val = Math.min(maxx,
(Math.ceil(i * j) - 1.0));
let times = (freq[i] -
freq[i - 1]),
con = (j - 0.5);
// nos. in [(n-0.5)X, (n+0.5)X)
// range will add n to the ans
ans += times * con * (freq[val] -
freq[cur]);
cur = val;
if (val == maxx)
break;
}
}
}
// Return the final result
return ans;
}
// Driver Code
let arr = [ 1, 2, 3 ];
let n = arr.length;
document.write(func(arr, n));
</script>
12
Complejidad de tiempo: O(N * log (N) ) , donde N representa el tamaño de la array dada.
Espacio auxiliar: O(100005) , no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por KrishnaHare y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA