Discussion on 'Count Divisors' (Problem from Hacker Earth)

To See All Articles About Technology: Index of Lessons in Technology

Try it out

Problem

You have been given 3 integers: l, r and k. Find how many numbers between l and r (both inclusive) are divisible by k. You do not need to print these numbers, you just have to find their count.

Input Format
The first and only line of input contains 3 space separated integers l, r and k.

Output Format
Print the required answer on a single line.

Constraints
1 <= l <= r <= 1000

1 <= k <= 1000

Sample Input
1 10 1
Sample Output
10

Time Limit: 1
Memory Limit: 256
Source Limit:

Psuedocode

if (r - l + 1) > k
    return (r - l + 1) / k
else:
    if floor(l / k) == floor(r / k):
        return 0
    else:
        return 1

Critique this psuedocode.

Solution

Your pseudocode is heading in the right direction by trying to find how many numbers in the range [l, r] are divisible by k, but it still contains logical issues. Let’s break it down carefully and critique each part:

Goal
We want to count all numbers x such that l ≤ x ≤ r and x % k == 0.

 Issues in Your Pseudocode
Your pseudocode:

if (r - l + 1) > k
    return (r - l + 1) / k
else:
    if floor(l / k) == floor(r / k):
        return 0
    else:
        return 1

Problem 1: (r - l + 1) / k doesn't count multiples of k
This gives the average number of elements between l and r per k steps, not how many elements are divisible by k.

Consider l = 3, r = 10, k = 2

r - l + 1 = 8

8 / 2 = 4 ✅ correct here by luck

But try l = 5, r = 15, k = 3:

r - l + 1 = 11, 11 / 3 = 3 ❌ wrong (actual count: 4 → 6, 9, 12, 15)

🔴 Problem 2: Your else block logic is oversimplified
plaintext
Copy
Edit
if floor(l / k) == floor(r / k):
    return 0
else:
    return 1
This assumes that at most one number divisible by k exists in [l, r], which is incorrect.

For example, l = 3, r = 10, k = 2:

floor(3/2) = 1, floor(10/2) = 5 → not equal → returns 1 ❌ but actual count is 4

✅ Correct and Simple Pseudocode

Input: l, r, k

# Use integer division (i.e., floor)
count = floor(r / k) - floor((l - 1) / k)

Return count
✅ Why this Works
Let’s take l = 5, r = 15, k = 3

Numbers ≤ 15 divisible by 3: 3, 6, 9, 12, 15 → total = floor(15/3) = 5

Numbers ≤ 4 divisible by 3: 3 → total = floor(4/3) = 1

So numbers divisible by 3 in [5, 15] = 5 - 1 = 4

💡 Final Thoughts
❌ Avoid using (r - l + 1) / k unless l = 1 and k = 1

✅ Stick to the formula floor(r / k) - floor((l - 1) / k) for correct results in all ranges

Would you like a Python function implementing this pseudocode too?
    
Explanation

✅ Correct Way to Count Multiples of k in [l, r]
The correct formula is:

count = floor(r / k) - floor((l - 1) / k)
It works because:

floor(r / k) counts how many numbers from 1 to r are divisible by k

floor((l - 1) / k) counts how many from 1 to l-1 are divisible by k

Subtracting the two gives how many are in the range [l, r]