Member Avatar for woojungkyu

What is the best algorithm for finding the number of integers divisible by X?

I can easily do a:

for(num=1;num<maxRange;num++) {
int result = 0;
if(num%Y==0) {
result++;
}
}

but what if the maxRange is a really huge number (say a 9 or 10 digit number)?
I need something which is faster than the algorithm above.

Edited by woojungkyu because: Keep It Clear - Do use code tags when posting any code
  • 4 Contributors
  • 7 Replies
  • 190 Views
  • 18 Hours Discussion Span
  • Latest Post Latest Post by Member #647493

Dani AI

Generated

A faster, constant-time solution is to avoid any loop and count multiples by arithmetic. As hinted, the number of integers divisible by |X| up to N is floor(N / |X|). So for an inclusive interval [min, max] you subtract the count below min from the count up to max. ’s modulo idea and ’s “jump by X” loop are fine for some cases, but the arithmetic method is O(1) and avoids iterating large ranges.

Use Java’s floor-aware helpers to handle negative endpoints correctly and avoid the min-1 overflow. Example implementation (robust for typical 64-bit ranges):

public static long countMultiplesInRange(long min, long max, long x) {
    if (x == 0) throw new IllegalArgumentException("divisor must not be zero");
    if (min > max) return 0;

    long d = x >= 0 ? x : -x;
    if (d < 0) throw new IllegalArgumentException(
        "absolute value of divisor overflows (use BigInteger)");

    long upToMax = Math.floorDiv(max, d);
    long belowMin = Math.floorDiv(min, d) - (Math.floorMod(min, d) == 0 ? 1L : 0L);
    return upToMax - belowMin;
}

Notes and pitfalls:

  • For positive ranges you can use plain integer division (e.g., max / x - (min-1) / x), but that breaks with negatives or when min-1 would overflow.
  • Use long when ranges or X can exceed 2,147,483,647. If you must support values outside 64-bit, switch to BigInteger.
  • x must not be zero; treat negative divisors by absolute value (divisible by -3 is same as by 3).
  • The result is O(1) time and uses only a few integer operations — ideal when maxRange is huge (9–10 digits or larger).

Recommended Answers

All 7 Replies

Member Avatar for JamesCherrill

Isn't it just maxRange/X?

Member Avatar for woojungkyu

Isn't it just maxRange/X?

I'm a bit confused? What if the minimum range changes?
like instead of starting from 1 it starts with 200... etc?

And how accurate is it when lets say
max=1000, X=6? >_<

Edited by woojungkyu because: n/a
Member Avatar for JamesCherrill

Then isn't it just max/X - (min-1)/x ??? (ie subtract the ones below the min)
(I'm not certain about this, but if you have working code now you could try this and see if it gives the same answers)

commented: I agree, unless min must not be excluded +5
Member Avatar for woojungkyu

Then isn't it just max/X - (min-1)/x ??? (ie subtract the ones below the min)
(I'm not certain about this, but if you have working code now you could try this and see if it gives the same answers)

oohh.. that might work.. >_<
Because what I did at first was to subtract the min from the max then divide. :D
Sorry. :<

Also tried doing this:

for (i = min; i <= max; i += X)
    {
        result++;
    }

just in case.. >_<

Edited by woojungkyu because: n/a
Member Avatar for Member #647493

Instead of incrementing your test number by 1, you can increment your test number by X,
But only once you find the first test number that works.

int Min = 10;
int Max = 100;
int Divisor = 27;
int Test = Min;
int Jump = 1;
int Count = 0;

while (Test <= Max)
{
   if (Test % Divisor == 0)
   {
      Count++;
      Jump = Divisor;
   }
   Test = Test + Jump;
}
Member Avatar for Taywin

What you need to do will be separated into 2 parts - find the first divisible number and a loop which is increment by X up to the max. The second part is easy and you should be able to do it. Now we need to talk about the first part.

hfx642 algorithm is OK but it is a brute-force which could be costly. If let say min is 1234, max is 987654321, and X is 999999, How many times do you have to go through the loop to find the first divisible number?

What you could actually do is a simple arithmetic. Think about it. If the X value is already a divisible value of the min, the min itself is already the first divisible number, correct? Now, if it is not, then the modulo value could be used to find the first divisible number! *hint hint*

PS: You also need to check whether X is less than max before you attempt to find the first divisible number.

Edited by Taywin because: n/a
Member Avatar for Member #647493

Ooooooo... Modulo!!
Yes... Use THAT to get your first number, THEN increment by your divisor.
Good idea!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.