Jahongir Rahmonov - 15 days ago 4

Python Question

Let's say I have two numbers: 6 and 11 and I am trying to find how many numbers between this range are divisible by 2 (3, in this case).

I have this simple code right now:

`def get_count(a, b, m):`

count = 0

for i in range(a, b + 1):

if i % m == 0:

count += 1

return count

Its order of growth is linear, O(N), I believe.

I was wondering if there is a faster algorithm with a constant O(1) performance, or a mathematical formula.

I don't expect a direct answer. The name of such an algorithm would be awesome.

Thank you.

Answer

`((b - b%m) - a)//m+1`

seems to work for me. I doubt it has a name. Another formula that seems to work is `(b//m) - ((a-1)//m)`

.

Sample python3 program:

```
def get_count(a, b, m):
return (((b - (b % m)) - a) // m) + 1
for i in range(5, 8):
for j in range(10, 13):
print(get_count(i, j, 2), end=" ")
print()
```

Source (Stackoverflow)

Comments