Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Moderator Note: This is a question in a current contest.

Given two numbers $M$ and $N$, Let $q_i$ be the integer part of $\frac{iN}{M}$. What is $$ \sum_{i=0}^{M-1} q_i? $$ The Sum is obviously can be calculated in $O(M)$. Can this be done in less time, maybe $O(1)$ if there exists some simpler reduced expression?


EDIT: This is a question from an ongoing competition, as noted by noob in an answer below and link compliments of Martin Sleziak.

share|improve this question
1  
Why is it $O(M)$? If $N=M$, the sum is $M(M-1)/2$, which is $O(M^2)$. –  user1551 Mar 9 '13 at 8:23
    
Is there any special relationship between M and N? For example, if M and N are coprime, I believe the calculation could be done in O(1) time. –  Mike Mar 9 '13 at 8:36
    
I edited... It was sum to calculated in O(M) –  Shashwat Kumar Mar 9 '13 at 8:37
2  
I got the solution. It is O(log n*log m). sum = (NM - N - M + gcd(N, M))/2) –  Shashwat Kumar Mar 9 '13 at 8:38
1  
This is a question in IOPC 2013 being held on Codechef at present. Please refrain from asking questions like this during the contest. Its not in the spirit of the contest. Moderators please close down this question. –  user65917 Mar 9 '13 at 9:15
show 3 more comments

1 Answer

Assuming M and N are integers, I believe your formula can be rewritten as

$$\sum\limits_{i=0}^{M-1}\frac{iN}M-\frac1M\sum\limits_{i=0}^{M-1}iN \mod M.$$

The first sum is an arithmetic sum. There is a formula for arithmetic sums that can be done in O(1) time. The second summation is the sum of remainders from the division. If $N$ and $M$ are coprime, no 2 of these remainders are the same, reducing the sum to $\sum\limits_{i=0}^{M-1}i$, which is another arithmetic sum.

I'm sure the formula can be adjusted in the case where $M$ and $N$ are not coprime. Maybe someone else can fill in the blanks while I'm getting some sleep, assuming you're interested. My guess is if you know nothing about M and N, your computation time will stem from performing the Euclidean algorithm to obtain a gcd, which I believe should be less than linear time.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.