Skip to content

Instantly share code, notes, and snippets.

@klmr
Created June 10, 2012 10:29
Show Gist options
  • Save klmr/2904851 to your computer and use it in GitHub Desktop.
Save klmr/2904851 to your computer and use it in GitHub Desktop.
Different methods of counting multiples of k
public static long CountDiv1(int a, int b, int k) {
if (k < 0)
return CountDiv1(a, b, -k);
// Adapt this if one of the bounds is exclusive.
long range = (long) b - (long) a + 1;
// Get the rough number of elements in the range.
long number = range / k;
// We undercounted by one element if the range isn't evenly
// divisible by k and the remainder covers a value which is.
// In particular, that value can lie towards either end of the range
long remainder = range % k;
if (remainder != 0) {
bool found = false;
for (long i = 0; i <= remainder / 2; i += 1)
if ((a + i) % k == 0 || (b - i) % k == 0)
found = true;
if (found)
number += 1;
}
return number;
}
public static long CountDiv2(int ia, int b, int k) {
if (k < 0)
return CountDiv2(ia, b, -k);
// Necessary for a = int.MinValue since -int.MinValue overflows.
long a = ia;
if (a > 0 && b > 0)
return b / k - (a - 1) / k;
if (a < 0 && b < 0)
return -a / k - (-b - 1) / k;
// +1 since 0 is also divisible by k.
return -a / k + b / k + 1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment