Given an array arr[] of N positive integers. For all the possible pairs (x, y) the task is to find the summation of x/y.
Note: If decimal part of (x/y) is &ge 0.5 then add ceil of (x/y), else add floor of (x/y).
Examples:
Input: arr[] = {1, 2, 3}
Output: 12
Explanation:
All possible pairs with division are:
(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
Sum = 1 + 1 + 0 + 2 + 1 + 1 + 3 + 2 + 1 = 12.
Input: arr[] = {1, 2, 3, 4}
Output: 22
Explanation:
All possible pairs with division are:
(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
Sum = 1 + 1 + 0 + 0 + 2 + 1 + 1 + 1 + 3 + 2 + 1 + 1 + 4 + 2 + 1 + 1 = 22.
Naive Approach: The idea is to generate all the possible pairs in the given array and find the summation of (x/y) for each pair (x, y).
Time Complexity: O(N2)
Efficient Approach:
To optimize the above method we have to compute the frequency array where freq[i] denotes the number of occurrences of number i.
- For any given number X, all the numbers ranging from [0.5X, 1.5X] would result in contributing 1 to the answer when divided by X. Similarly all the numbers ranging from [1.5X, 2.5X] would result in contributing 2 to the answer when divided by X.
- Generalizing this fact all the numbers ranging from [(n-0.5)X, (n+0.5)X] would result in contributing n to the answer when divided by X.
- Thus for every number P in the range 1 to N we can get the count of the numbers which lie in the given range [L, R] by just computing a prefix sum of frequency array.
- For a number P, we need to query on the ranges at most N/P times.
Below is the implementation of the above approach:
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 longusing namespace std;// Function to compute the sumint 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 codeint 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 arrayclass GFG{// Function to compute the sumstatic 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 codepublic 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 arrayfrom math import *# Function to compute the sumdef 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 codeif __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 arrayusing System;class GFG{// Function to compute the sumstatic 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 codepublic 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 sumfunction 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> |
Output:
12
Time Complexity: O(N * log (N) ), where N represents the size of the given array.
Auxiliary Space: O(100005), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
