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

Question

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?

Answer 1

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.

Answer 2

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