Given an array arr[] of size N, the task is to find the sum of the floor value of (arr[i] / arr[j]) for all pairs of indices (i, j).
Examples:
Input: arr[] = { 1, 2, 3 }
Output: 9
Explanation:
Sum = (arr[i] / arr[j]) (a[0] / a[0]) + (a[0] / a[1]) + (a[0] / a[2]) + (a[1] / a[1]) + (a[1] / a[2]) + (a[2] / a[2]) + (a[1] / a[0]) + (a[2] / a[0]) + (a[2] / a[1]) = 1 + 0 + 0 + 1 + 0 + 1 + 2 + 3 + 1 = 9
Therefore, the required output is 9.Input: arr[] = { 4, 2, 5, 6 }
Output: 14
Naive Approach: The simplest approach to solve this problem is to generate all possible pairs of the array and for each pair, increment the result by the floor value of (arr[i] / arr[j]). Finally, print the result obtained.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized based on the following observation:
If a sequence is X, X + 1, …, 2 * X – 1, 2 * X, …., 3 * X – 1
(X) / X + (X + 1) / X + … + (2 * X – 1) / X + (2 * X) / X + … + (3 * X – 1) / X
= 1 + 1 + … + 1 + 2 + … + 2
For the first X consecutive numbers, the floor value of (X + i) / X = 1
For the next X consecutive numbers, the floor value of (2 * X + i) / X = 2
and so on…
Follow the steps below to solve the problem:
- Initialize an array, say freq[], to store the frequency of array elements.
- Initialize an array, say preFreq[], to store the prefix sum of count[] array.
- preFreq[j] – preFreq[i] stores the count of array elements whose values lies in the range [i, j].
- Find the largest element in the array say, Max.
- Iterate over the range [1, Max]. For every ith value, count the array elements whose value lies in the range [i, j], using the preFreq[] array, where j is a multiple of i and increment the result by frequency[i] * (preFreq[j – 1] – preFreq[j – i – 1]) * (j / i – 1).
- Finally, print the result obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Stores the maximum value of // an array element const int N = 3e5; // Function to find the sum of // floor(a[i]/a[j]) of all pairs (i, j) void getFloorSum(int arr[], int n) { // Stores frequency of // array element int freq[N] = { 0 }; // Stores prefix sum // array of frequency[] int preFreq[N] = { 0 }; // Traverse the array for (int i = 0; i < n; i++) { // Update frequency // of arr[i] freq[arr[i]]++; } // Compute the prefix sum // of frequency[] for (int i = 1; i < N; i++) { preFreq[i] = preFreq[i - 1] + freq[i]; } // Stores the sum of floor(a[i]/a[j]) // of all pairs (i, j) int ans = 0; // Iterate over the range [1, Max] for (int i = 1; i <= N; i++) { // Find the count of numbers in // the range [i * K, i * (K + 1)) // and update the result for (int j = i; j <= N; j += i) { // Stores count of numbers // in range[j - i - 1, j - 1] int X = (preFreq[j - 1] - preFreq[j - i - 1]); // Update ans ans += X * (j / i - 1) * freq[i]; } } // Print the answer cout << ans; } // Driver Code int main() { // Given array int arr[] = { 1, 2, 3 }; // Stores the size of array int n = sizeof(arr) / sizeof(arr[0]); getFloorSum(arr, n); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Stores the maximum value of // an array element static int N = (int) 3e5; // Function to find the sum of // Math.floor(a[i]/a[j]) of all pairs (i, j) static void getFloorSum(int arr[], int n) { // Stores frequency of // array element int freq[] = new int[N]; // Stores prefix sum // array of frequency[] int preFreq[] = new int[N]; // Traverse the array for (int i = 0; i < n; i++) { // Update frequency // of arr[i] freq[arr[i]]++; } // Compute the prefix sum // of frequency[] for (int i = 1; i < N; i++) { preFreq[i] = preFreq[i - 1] + freq[i]; } // Stores the sum of Math.floor(a[i]/a[j]) // of all pairs (i, j) int ans = 0; // Iterate over the range [1, Max] for (int i = 1; i < N; i++) { // Find the count of numbers in // the range [i * K, i * (K + 1)) // and update the result for (int j = i; j < N; j += i) { // Stores count of numbers // in range[j - i - 1, j - 1] int X = (preFreq[j - 1] - preFreq[(Math.abs(j - i - 1))]); // Update ans ans += X * (j / i - 1) * freq[i]; } } // Print the answer System.out.print(ans); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1, 2, 3 }; // Stores the size of array int n = arr.length; getFloorSum(arr, n); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program to implement # the above approach # Stores the maximum value of # an array element N = 10**5 # Function to find the sum of # floor(a[i]/a[j]) of all pairs (i, j) def getFloorSum(arr, n): # Stores frequency of # array element freq = [ 0 for i in range(N + 1)] # Stores prefix sum # array of frequency[] preFreq = [ 0 for i in range(N + 1)] # Traverse the array for i in range(n): # Update frequency # of arr[i] freq[arr[i]] += 1 # Compute the prefix sum # of frequency[] for i in range(1, N): preFreq[i] = preFreq[i - 1] + freq[i] # Stores the sum of floor(a[i]/a[j]) # of all pairs (i, j) ans = 0 # Iterate over the range [1, Max] for i in range(1, N + 1): # Find the count of numbers in # the range [i * K, i * (K + 1)) # and update the result for j in range(i, N + 1, i): # Stores count of numbers # in range[j - i - 1, j - 1] X = (preFreq[j - 1] - preFreq[j - i - 1]) # Update ans ans += X * (j // i - 1) * freq[i] # Prthe answer print(ans) # Driver Code if __name__ == '__main__': # Given array arr = [1, 2, 3] # Stores the size of array n = len(arr) getFloorSum(arr, n) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; class GFG{ // Stores the maximum value of // an array element static int N = (int)3e5; // Function to find the sum of // Math.Floor(a[i]/a[j]) of all // pairs (i, j) static void getFloorSum(int []arr, int n) { // Stores frequency of // array element int []freq = new int[N]; // Stores prefix sum // array of frequency[] int []preFreq = new int[N]; // Traverse the array for(int i = 0; i < n; i++) { // Update frequency // of arr[i] freq[arr[i]]++; } // Compute the prefix sum // of frequency[] for(int i = 1; i < N; i++) { preFreq[i] = preFreq[i - 1] + freq[i]; } // Stores the sum of Math.Floor(a[i]/a[j]) // of all pairs (i, j) int ans = 0; // Iterate over the range [1, Max] for(int i = 1; i < N; i++) { // Find the count of numbers in // the range [i * K, i * (K + 1)) // and update the result for(int j = i; j < N; j += i) { // Stores count of numbers // in range[j - i - 1, j - 1] int X = (preFreq[j - 1] - preFreq[(Math.Abs(j - i - 1))]); // Update ans ans += X * (j / i - 1) * freq[i]; } } // Print the answer Console.Write(ans); } // Driver Code public static void Main(String[] args) { // Given array int []arr = { 1, 2, 3 }; // Stores the size of array int n = arr.Length; getFloorSum(arr, n); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // Stores the maximum value of // an array element var N = 1000; // Function to find the sum of // floor(a[i]/a[j]) of all pairs (i, j) function getFloorSum(arr, n) { // Stores frequency of // array element var freq = Array(N).fill(0); // Stores prefix sum // array of frequency[] var preFreq = Array(N).fill(0); // Traverse the array for (var i = 0; i < n; i++) { // Update frequency // of arr[i] freq[arr[i]]++; } // Compute the prefix sum // of frequency[] for (var i = 1; i < N; i++) { preFreq[i] = preFreq[i - 1] + freq[i]; } // Stores the sum of floor(a[i]/a[j]) // of all pairs (i, j) var ans = 0; // Iterate over the range [1, Max] for (var i = 1; i <N; i++) { // Find the count of numbers in // the range [i * K, i * (K + 1)) // and update the result for (var j = i; j <N; j += i) { // Stores count of numbers // in range[j - i - 1, j - 1] var X = (preFreq[j - 1] - preFreq[(Math.abs(j - i - 1))]); // Update ans ans += X * (parseInt(j / i) - 1) * freq[i]; } } // Print the answer document.write( ans); } // Driver Code // Given array var arr = [1, 2, 3 ]; // Stores the size of array var n = arr.length; getFloorSum(arr, n); </script> |
Output:
9
Time Complexity: O(N + M * log(log(M)), where M is the largest array element
Auxiliary Space: O(M)
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!
