-1

Given two numbers M and N. Let qi be integer part of i*N/M. What is the sum of qi's over i from 0 to M-1. O(M) is the obvious method. Can this be done in less time, may be O(1) if there exists some simpler reduced expression?

Shashwat Kumar
  • 5,159
  • 2
  • 30
  • 66

2 Answers2

3

Interesting question. (This post will make me wish we had math formatting on SO...)

My approach is to write the problem as

∑i floor(i*N/M) = ∑i i*N/M - ∑i [i*N/M]

where [] is the "fractional-part-of" operator (i.e. [1.3] = 0.3, [6] = 0, etc.).

Then, the first half is easy: it's a normal arithmetic sequence sum multiplied by N/M, so it sums to N*(M-1)/2. The second half is trickier to deal with, but you'll see why it is crucial to separate it from the first half.

Let k = gcd(N, M). Then, let n = N/k and m = M/k, so the second half is ∑i [i*n/m]. Crucially, n and m are now relatively prime. The sum over i is from 0 to M-1 = km-1. We can split i into a multiple of m and the remainder, as i = qm + r, so that the sum is now

∑q ∑r [r*n/m]

where q sums from 0 to k-1 and r sums from 0 to m-1. Now comes the critical step: because n and m are relatively prime, the sequence r*n for r = 0..m-1 is a permutation of 0, 1, 2, 3, ..., m-1 mod m. Therefore, the sequence [r*n/m] is a permutation of 0/m, 1/m, 2/m, ..., (m-1)/m, and so ∑r [r*n/m] = ∑r r/m = m*(m-1)/2/m = (m-1)/2. Thus, the entire sum collapses to k * (m-1)/2 = (km - k) / 2 = (M - k) / 2.

Finally, we combine the halves: N*(M-1)/2 - (M-k)/2 = (NM - N - M + k)/2.

Thus, the desired sum is (NM - N - M + gcd(N, M))/2. Calculating the GCD can be done relatively quickly using Euclid's algorithm, so this will be fairly fast to calculate.

Community
  • 1
  • 1
nneonneo
  • 171,345
  • 36
  • 312
  • 383
0

It looks to me like you are trying to sum 0N/M + 1N/M + 2N/M + 3N/M ... (M-1)N/M. If so, you have (0+1+2+3...+(M-1))N/M. You can solve that in O(1) because (0+1+2+3+...+(M-1)) is M*(M-1)/2. The M's cancel and you get (M-1)N/2.

kainaw
  • 4,256
  • 1
  • 18
  • 38