1

I created an algorithm for finding the number of numbers inside a range that are divisible by a third number k. I got this to work but in polynomial time instead of linear time

function divisibleCount(x, y, k) {
    var count = 0;
    for (var i = x; i <= y; i++) {
        if (i % k === 0) {
            count++;
        }
    return count;
}

The arguments are as follows

x: Start of range
y: End of range
K: Number is divisible by

The problem is definitely the for loop which makes this polynomial time.

I attempted to use

for (var i = x; i <= k; i += k)

but got the wrong answer.

Is there any way I can improve this?

user5680735
  • 703
  • 2
  • 7
  • 21
  • How a simple loop might cause polynomial time? – zerkms Mar 09 '16 at 00:21
  • Since this works and you're looking for ways to improve it, this may be a a better candidate for http://codereview.stackexchange.com than here. – jfriend00 Mar 09 '16 at 00:21
  • "but got the wrong answer." --- since you need to find the first number that is divisable by `k`, then divide what's left by `k` slices – zerkms Mar 09 '16 at 00:23
  • I had the right answer when using ++ but not when trying to be more efficient – user5680735 Mar 09 '16 at 00:24
  • @zerkms - no need to find anything, just `%`. – Amit Mar 09 '16 at 00:24
  • @Amit "just `%`" - is how you find if a number is divisable by another number. I did not say one must use loops for that. – zerkms Mar 09 '16 at 00:24
  • 1
    I'm just dying to know what the `y` argument is for ? – adeneo Mar 09 '16 at 00:25
  • @zerkms and is also how you can *calculate* the first number, without looking for it. – Amit Mar 09 '16 at 00:25
  • @Amit that is indeed correct. "without looking for it" --- I did not suggest to use loops anywhere, not sure why you think I did. – zerkms Mar 09 '16 at 00:26
  • Did you mean `i <= y`? – Bergi Mar 09 '16 at 00:28
  • 2
    Find the number number of numbers between 0 and y divisible by k by dividing y by k and rounding down. Do the same thing for x, and subtract the second number from the first. – Pointy Mar 09 '16 at 00:29
  • @zerkms I have been off by one since birth so I just fix it once I've coded it up :) *edit* probably should be between 1 and y, not zero. – Pointy Mar 09 '16 at 00:31
  • 4
    Your working solution is `O(max(y-x, 0))` (assuming constant time for arithmetic operations). That's linear, not polynomial time. Regardless, you should be able to find the solution in constant time (`O(1)`) – Bergi Mar 09 '16 at 00:32
  • Possible duplicate of [Faster algorithm to count how many numbers are divisible by a specific integer in a range](http://stackoverflow.com/questions/26777546/faster-algorithm-to-count-how-many-numbers-are-divisible-by-a-specific-integer-i) – 200_success Mar 09 '16 at 00:58

1 Answers1

6

O(1).

Something like this:

Math.floor((y-1) / k) - Math.floor((x-1) / k)

Explanation:

Math.floor((x-1) / k) is the number of numbers divisible by k before the interval.

Math.floor((y-1) / k) is the number of numbers divisible by k up to the end of the interval.

Should be right for positive numbers and k > 0. Hopefully ;)

Edit: I see, you want to include y in the range. Ok, then change to:

Math.floor(y / k) - Math.floor((x-1) / k)

Is this for an assignment? I feel a little guilty.

Alberto Chiesa
  • 7,022
  • 2
  • 26
  • 53
  • 1
    `x=2; y=4; k=2`. Expected: 2, actual: 1 – zerkms Mar 09 '16 at 00:41
  • @zerkms, this is correct for a standard interpretation of "in the range between 2 and 4", which typically includes 2 but not 4. Other interpretations are possible, but you didn't specify one! – senderle Mar 09 '16 at 00:58
  • 2
    @senderle 1. I'm not an OP 2. OPs reference implementation represents a range as `[x; y]` – zerkms Mar 09 '16 at 01:03