1+1/2+1/3+1/4…1/n = log n

Problem

We have a nice problem today (May 15) on leetcode biweekly contest. It needs us to know the fact of

1+1/2+1/3+1/4…1/n = log n

1862. Sum of Floored Pairs

Explanation

Suppose we have the nums in sorted order.

[x1, x2, x3, …]

For each x, traverse the j from 1 to n to find the numbers in the following region

[x*j, x*(j+1))

In order to counter how many number in the region of [a, b), we can use a prefix frequency sum to computer the result in O(1).

We also need consider the special case of same numbers such as

[7, 7, 7, 7]

In this case, the result is Len(nums)*(Len(nums)-1) based on the multiplication rule.

Complexity

[x1, x2, x3, …MX]

Where MX is the maximum value as we sort the nums first.

Let’s think about the special case of ,

[1, 2, 3, 4, 5, 6]

For

• x = 1, j can be 1, 2, 3, … 6 which is 6
• x = 2, j can be 1, 2, 3 , which is 6/2
• x = 3, j can be 1, 2, which is 6/3
• x = 4, j can be 1, which is 6/4

In a general case, j are from

n, n/2, n/3, …

sum(n, n/2, n/3, …) = n*(sum(1, 1/2, 1/3, …1/n)) = n log n

See this article to find how to compute sum(1, 1/2, 1/3, …1/n)

So the complexity is O(n log n)

Code

// set N as two times larger to get rid of out of boundary issue
const int N = 200010;
int cnt[N];
const int mod = 1e9 + 7;
class Solution {
public:
    int sumOfFlooredPairs(vector<int>& a) {
        const int n = a.size();
        memset(cnt, 0, sizeof cnt);
        long long ret = 0, thisret = 0;
        for (auto &x:a) cnt[x]++;
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        const int m = a.size();
        int mx = a.back();
        vector<int> prefixsum(N, n);
        prefixsum[0] = 0;
        for (int i = 1; i <=mx; ++i) {
            prefixsum[i] = prefixsum[i-1] + cnt[i];
        }
        for (auto &x: a) {
            // for the same number such as [7, 7, 7, 7]
            ret += cnt[x]*(cnt[x] - 1);
            int lower, upper;
            for (int j = 1; x*j <= mx; ++j) {
                lower = x*j;
                upper = x*(j+1) - 1;
                if(j == 1) ret += (long long)cnt[x]*j*(prefixsum[upper] - prefixsum[lower]);
                else ret +=  (long long)cnt[x]*j*(prefixsum[upper] - prefixsum[lower - 1]);
            }
        }
        // for the num itself
        ret += n;
        return ret % mod;
    }
};

A more concised code adjusted from [1]

typedef long long LL;
const int N = 100010, MOD = 1e9 + 7;
int s[N];
class Solution {
public:
    int sumOfFlooredPairs(vector<int>& nums) {
        memset(s, 0, sizeof s);
        // get the count for nums
        for (auto &x : nums) s[x]++;
        // compute prefix frequency inplace
        for (int i = 1; i < N; ++i) s[i] += s[i-1];
        int ret = 0;
        for (int i = 1; i < N; ++i)
            for (int j = 1; i*j < N; ++j)
            {
                int l = i * j, r = min(N -1, i * (j + 1) - 1);
                // s[i] - s[i-1] is the count of i
                ret += (s[i] - s[i-1])*j*(s[r] - s[l-1]); 
                ret %= MOD;
            }
        return ret;
    }
};

Reference

[1] https://www.acwing.com/activity/content/code/content/1239353/