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

Popular posts from this blog

linux - Does gcc have any options to add version info in ELF binary file? -

android - send complex objects as post php java -

charts - What graph/dashboard product is facebook using in Dashboard: PUE & WUE -