sum-of-floored-pairs

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an integer array <code>nums</code>, return the sum of <code>floor(nums[i] / nums[j])</code> for all pairs of indices <code>0 &lt;= i, j &lt; nums.length</code> in the array. Since the answer may be too large, return it modulo <code>109 + 7</code>.

The <code>floor()</code> function returns the integer part of the division.

&nbsp;
Example 1:

<pre>
Input: nums = [2,5,9]
Output: 10
Explanation:
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
We calculate the floor of the division for every pair of indices in the array then sum them up.
</pre>

Example 2:

<pre>
Input: nums = [7,7,7,7,7,7,7]
Output: 49
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>

sumOfFlooredPairs

Sum of Floored Pairs

Array

Math

Binary Search

Prefix Sum

给你一个整数数组 <code>nums</code> ，请你返回所有下标对 <code>0 &lt;= i, j &lt; nums.length</code> 的 <code>floor(nums[i] / nums[j])</code> 结果之和。由于答案可能会很大，请你返回答案对<code>109 + 7</code> 取余 的结果。

函数 <code>floor()</code> 返回输入数字的整数部分。

 

示例 1：

<pre>输入：nums = [2,5,9]
输出：10
解释：
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
我们计算每一个数对商向下取整的结果并求和得到 10 。
</pre>

示例 2：

<pre>输入：nums = [7,7,7,7,7,7,7]
输出：49
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>