CODEWITHSUNDEEP
c++algorithmmath
Yeasin Mollik
Yeasin Mollik

Reputation: 531

How to find the number of values in a given range that has a certain remainder when divided by a given number?

Given four integers N, L, R and Rem. I have to find the the number of values between L and R(inclusive) that gives remainder Rem when divided by N.

For example: If N = 3, L = 2, R = 10 and Rem = 1 then the numbers with remainder 1 when divided by 3 in this range are {4, 7, 10}. So, the answer is 3.

Here is the brute force approach I coded: 

int main() {
    int N, L, R, Rem;
    cin >> N >> L >> R >> Rem;

    int Ans = 0;
    for (int i = L; i <= R; i++) {
        if (i % N == Rem)
            Ans++;
    }
    cout << Ans << endl;
}

What would be a better approach to solve this problem?

Upvotes: 3

Views: 999

Answers (4)

Aviad Rozenhek
Aviad Rozenhek

Reputation: 2409

TLDR it is roughly (R-L+1)/N give or take +- 1

for instance L=2 R=10 N=3 REM=0

the numbers are 3,6,9 (R-L+1)/N = (10-2+1)/3 = 9/3 = 3

here's an accurate solution with explanation, that requires no loops

find the first number greater or equals to L that divides nicely by N

L = (L % N == rem)? L : L + (REM - L%N + N)%N

find the last number smaller or equals to R that divides nicely by N

R = (R % N == rem)? R : R - (N - (REM - R%N + N)%N)

the result is

int result = ((R-L)/N) + 1

Upvotes: 2

Ganesh Chowdhary Sadanala
Ganesh Chowdhary Sadanala

Reputation: 1278

Solution: The answer is floor((R-Rem)/N)-ceil((L-Rem)/N)+1 where ceil(a/b)=(a+b-1)/b floor(a/b) = a/b Assuming a and b are positive here. It does not work for negative numbers though.

Proof: Another way to think in terms of inequalities,

L<=N * K<=R

L<=N * K+1<=R

. . .

L<=N * K+N-1<=R

Note: Here K is the quotient (It is a pretty standard division rule learned in school)

To solve your case, consider the inequality

L<=N * K+Rem<=R

ceil((L-Rem)/N)<=K<=floor((R-Rem)/N)

so the answer is floor((R-Rem)/N)-ceil((L-Rem)/N)+1 where ceil(a/b)=(a+b-1)/b floor(a/b) = a/b Assuming a and b are positive here. It does not work for negative numbers though.

Upvotes: 0

Dave
Dave

Reputation: 9075

(R - L) / N 
+ 1 if (R - L) % N ≥ (rem - L) % N

Upvotes: 1

Evg
Evg

Reputation: 26282

First, find the number of such values in the range [0, n):

template<class T>
T count(T n, T div, T rem) {
    assert(rem < div);
    return (n + div - rem - 1) / div;
}

Then subtract, [0, max + 1) \ [0, min) = [min, max]:

template<class T>
T count(T min, T max, T div, T rem) {
    assert(min >= 0);
    assert(min <= max);
    return count(max + 1, div, rem) - count(min, div, rem);
}

Obviously, it doesn't work for negative values. The OP specified input as integers, not positive integers.

This answer assumes that all the integers are non-negative numbers. The reason is simple: we all agree on what the remainder is for non-negative numbers, but different definitions exist for negative ones. The problem wording says nothing about which definition should be taken. For example, in C++ itself before C++11, the standard specified the result of a % b to be implementation-defined if either a < 0 or b < 0. The reason is the following difference in how / operator is defined for integral operands:

  • Until C++11:

    The quotient is rounded in implementation-defined direction.

  • Since C++11:

    The quotient is truncated towards zero (fractional part is discarded).

Hence, % and std::div might give different results – before C++11, the latter function followed the "fractional part is discarded" rule.

Upvotes: 2

Related Questions