What is the simplest way to calculate the amount of even numbers in a range of unsigned integers?
An example: if range is [0...4] then the answer is 3 (0,2,4)
I'm having hard time to think of any simple way. The only solution I came up involved couple of if-statements. Is there a simple line of code that can do this without if-statements or ternary operators?
Pseudo code (i'm no C coder):
count = 0;
foreach(i in range){
if(i % 2 == 0){
count++;
}
}
Hint 1: The modulo operator will return the remainder of the current number
Hint 2: You don't need a for loop
Hint 3: A range is continuous
Hint 4: The number of even numbers in a continuous range are half even (sometimes half + 1, sometimes half - 1)
Hint 5: Building on Hint1: Consider also what (being + end + 1) % 2 gives
Hint 6: Most or all of the answers in this thread are wrong
Hint 7: Make sure you try your solution with negative number ranges
Hint 8: Make sure you try your solution with ranges spanning both negative and positive numbers
int even = (0 == begin % 2) ? (end - begin) / 2 + 1 : (end - begin + 1) / 2;
Which can be converted into:
int even = (end - begin + (begin % 2)) / 2 + (1 - (begin % 2));
EDIT: This can further simplified into:
int even = (end - begin + 2 - (begin % 2)) / 2;
EDIT2: Because of the in my opinion somewhat incorrect definition of integer division in C (integer division truncates downwards for positive numbers and upwards for negative numbers) this formula won't work when begin is a negative odd number.
EDIT3: User 'iPhone beginner' correctly observes that if begin % 2 is replaced with begin & 1 this will work correctly for all ranges.
I'd say
(max - min + 1 + (min % 2)) / 2
Edit: Erm okay for some reason I thought that (min % 2) returns 1 for even numbers.... :). The correct version is
(max - min + 1 + 1 - (min % 2)) / 2
or rather
(max - min + 2 - (min % 2)) / 2
int start, stop;
start = 0;
stop = 9;
printf("%d",(stop-start)/2+((!(start%2) || !(stop%2)) ? 1 : 0));
Where start and stop can hold any value. No need to iterate to to determine this number.
The count of even numbers between 0 and n is [n/2] + 1. Therefore the count of even numbers between (n + 1) and m is ([m/2] + 1) - ([n/2] + 1) = [m/2] - [n/2].
For count of even numbers between m and n the answer therefore would be [m/2] - [(n - 1)/2].
The [x] is taken to the direction of -\infty. Beware that the usual C integer division is not doing right in our case: a/2 is rounded towards zero, not -\infty, so the result will be not [a/2] for teh case of negative a.
This should be the simplest calculation; works for negative numbers, too. (Needs however that m >= n.) Doesn't contain ifs and ?:s.
If you don't consider negative numbers, you can use just m/2 - (n+1)/2 + 1, otherwise floor(m/2.0) - floor((n-1)/2.0)
The range is always [2a+b, 2c+d] with b,d = {0,1}. Make a table:
b d | #even
0 0 | c-a+1
0 1 | c-a+1
1 0 | c-a
1 1 | c-a+1
Now a = min/2, b = min % 2, c = max/2 and d = max % 2.
So int nEven = max/2 - min/2 + 1 - (min%2)
The first even number in the range is: (begin + 1) & ~1 (round begin up to even number).
The last even number in the range is: end & ~1 (round end down to even number).
The total number of even numbers in the range is therefore: (end & ~1) - ((begin + 1) & ~1) + 1.
int num_evens = (end & ~1) - ((begin + 1) & ~1) + 1;
Let's look at this logically ...
We have four cases ...
odd -> odd eg. 1 -> 3 answer: 1
odd -> even eg. 1 -> 4 answer: 2
even -> odd eg. 0 -> 3 answer: 2
even -> even eg. 0 -> 4 answer: 3
The first three cases can be handled simply as ...
(1 + last - first) / 2
The fourth case does not fall quite so nicely into this, but we can fudge around a little bit for it quite easily ...
answer = (1 + last - first) / 2;
if (both first and last are even)
answer++;
Hope this helps.
This'll do the trick, even for ranges with negative numbers.
int even = (last - first + 2 - Math.abs(first % 2) - Math.abs(last % 2)) / 2;
Tested with the following code:
public static void main(String[] args) {
int[][] numbers = {{0, 4}, {0, 5}, {1, 4}, {1, 5}, {4, 4}, {5, 5},
{-1, 0}, {-5, 0}, {-4, 5}, {-5, 5}, {-4, -4}, {-5, -5}};
for (int[] pair : numbers) {
int first = pair[0];
int last = pair[1];
int even = (last - first + 2 - Math.abs(first % 2) - Math.abs(last % 2)) / 2;
System.out.println("[" + first + ", " + last + "] -> " + even);
}
}
Output:
[0, 4] -> 3
[0, 5] -> 3
[1, 4] -> 2
[1, 5] -> 2
[4, 4] -> 1
[5, 5] -> 0
[-1, 0] -> 1
[-5, 0] -> 3
[-4, 5] -> 5
[-5, 5] -> 5
[-4, -4] -> 1
[-5, -5] -> 0
Oh well, why not:
#include <cassert>
int ecount( int begin, int end ) {
assert( begin <= end );
int size = (end - begin) + 1;
if ( size % 2 == 0 || begin % 2 == 1 ) {
return size / 2;
}
else {
return size / 2 + 1;
}
}
int main() {
assert( ecount( 1, 5 ) == 2 );
assert( ecount( 1, 6 ) == 3 );
assert( ecount( 2, 6 ) == 3 );
assert( ecount( 1, 1 ) == 0 );
assert( ecount( 2, 2 ) == 1 );
}
The answer:
(max - min + 2 - (max % 2) - (min % 2)) / 2
A short explanation:
odd..odd yields (length - 1) / 2
length = max - min + 1
Therefore, the answer is (length - 1) / 2 plus 1/2 for even min plus 1/2 for even max.
Note that (length - 1) / 2 == (max - min) / 2, and the "bonuses" are (1 - (min % 2)) / 2 and (1 - (max % 2)) / 2. Sum this all up and simplify to obtain the answer above.
I'm a bit surprised that iteration was tried to solve this.
The minimum number of even numbers possible in a range is equal to half of the length of the array of numbers, or, rangeEnd - rangeStart.
Add 1 if the first or last number is even.
So the method is: (using javascript)
function evenInRange(rangeStart, rangeEnd)
{
return
Math.floor(rangeEnd - rangeStart) +
((rangeStart % 2 == 0) || (rangeEnd % 2 == 0) ? 1 : 0)
}
Tests:
0 1 2 3 4 5 6 7 8
8 - 0 = 8
8 / 2 = 4
4 + 1 = 5
Even numbers in range:
0 2 4 6 8
11 12 13 14 15 16 17 18 19 20
20 - 11 = 9
9 / 2 = 4
4 + 1 = 5
Even numbers in range
12 14 16 18 20
1 2 3
3 - 1 = 2
2 / 2 = 1
1 + 0 = 1
Even numbers in range
2
2 3 4 5
5 - 2 = 3
3 / 2 = 1
1 + 1 = 2
Even numbers in range
2 4
2 3 4 5 6
6 - 2 = 4
4 / 2 = 2
2 + 1 = 3
Even numbers in range
2 4 6
There are (max - min + 1) numbers in the range for each case.
(max - min + 1)/2 even numbers in the range.(max - min + 1 - 1)/2, but because (max - min + 1) is odd, (max - min + 1)/2 will round down to the correct answer.(i+1)%2 == 1. So if both max and min are even, then (max + 1)%2 * (min + 1)%2 == 1. Luckily we want to add 1 when both max and min are even, so we just add this to our (max + min + 1)/2 formula.The nicely derived and easy to explain answer is
(max - min + 1)/2 + (max + 1)%2 * (min + 1)%2
edit:
(max - min + 1)/2 + Math.Abs((max + 1)%2 * (min + 1))%2
or (max - min + 1)/2 + |(max + 1)%2 * (min + 1)|%2
will fix the problem Vlad identifies, when min is negative and max is positive.
In terms of start and length:
(length >> 1) + (1 & ~start & length)
half the length plus 1 if start is even and length is odd.
In terms of start and end:
((end - start + 1) >> 1) + (1 & ~start & ~end)
half the length plus 1 if start is even and end is even.
This does not require any conditions at all:
evencount = floor((max - min)/2) + 1