c - O(1) code to count multiples of a number in a range? -
how do in constant time (i not want brute iterate b)?
// return number of multiples of c in [a,b] long count_multiples(int a, int b, int c) { assert(b >= && c != 0); // todo return -1; }
this question looks deceptively simple harder looks because has corner cases e.g. must handle cases (a
,b
can negative/zero , c
can negative , a
may equal b
may equal c
). result may not fit in 32-bit 1 case (a = 2^31
, b = 2^31-1
, c = 1 or -1
)
long count_multiples(int a, int b, int c) { if (b < a) return 0; if (c < 0) c = -c; long al = a, bl = b, cl = c; if (c == 1) return bl - al + 1; return ((bl + (b < 0 ? 1 : 0)) / cl) - ((al - (a > 0 ? 1 : 0)) / cl) + ((a <= 0 && b >= 0) ? 1 : 0); }
Comments
Post a Comment