Check if array has the same number of even and odd values in Python

Question

Task:
Complete the following function that determines if the number of even and odd values in an list of Integers is the same.

| In               | Out   |         Why            |
|------------------|-------|------------------------|
| [5, 1, 0, 2]     | true  | two evens and two odds |
| [5, 1, 0, 2, 11] | false | too many odds          |
| []               | true  | both have 0            |

The function should not affect the contents of the list.

My code:

def balanced(lst):
    n = len(lst)
    if n % 2 != 0:
        return False
    if n % 2 == 0:
        count_1 = 0
        count_2 = 0
        for item in lst:
            if item % 2 == 0:      #even
                count_1 += 1
            if item % 2 != 0:       #odd
                count_2 += 1
    if count_1 == count_2:
        return True
    else:
        return False
def result(lst):
     if balanced(lst):
         print("Your list is successfully balanced! It has same number of evens and odds!!")
     else:
         print("Oh no! Sorry! Your list seems to be not balanced! Try another list please!")
def main():
     lst_1 = [1,2,3,5,6,8,5,9]
     lst_2 = []
     lst_3 = [2,4,5,7]
     lst_4 = [1,2,4,4]
     lst_5 = [1,2,3]
     result(lst_1)
     result(lst_2)
     result(lst_3)
     result(lst_4)
     result(lst_5)
main()

Answer 1

There's no need to keep counts at all. All you need to do is keep track of whether the sequence is balanced or not as you check every element. And the special tests you had for an empty list or odd list length are redundant.

def balanced(lst):
    tilt = 0
    for item in lst:
        if item % 2 == 0:      #even
            tilt += 1
        else:                  #odd
            tilt -= 1
    return tilt == 0

Or if you prefer terseness over readability, you can turn it into a one-liner.

def balanced(lst):
    return sum(1 if item % 2 else -1 for item in lst) == 0

Answer 2

There are a few optimizations that seem obvious to me, but the algorithm seems fine for what is does.

if n % 2 != 0:
    return False
if n % 2 == 0:
    # ...

There is no need for the second if statement, as you already know that n % 2 == 0 is True, as you would have returned otherwise.

if item % 2 == 0:      #even
    count_1 += 1
if item % 2 != 0:       #odd
    count_2 += 1

You should use an if ... else construct, if the number isn't even, then it is odd. This makes one less check for each item.

if count_1 == count_2:
    return True
else:
    return False

You can simply return count_1 == count_2. This simplifies the code and saves a branch, making it slightly more efficient.

You could also use more meaningful variable names, and include a docstring documentating what the code does

Here is my take on your code:

def balanced(lst):
    '''Checks if a list contains the same amount of even and odd numbers'''

    if len(lst) % 2 != 0:
        return False
    count_even = 0
    count_odd = 0
    for item in lst:
        if item % 2 == 0:
            count_even += 1
        else: 
            count_odd += 1
    return count_even == count_odd

You could probably trim the code even more, for example using only one variable for counting, adding 1 on even numbers and subtracting 1 on odd numbers, and returning whether that value is 0, but I feel like it would affect negatively the readability.

Answer 3

• You don't need count_1 and count_2 just one count.

  $$ \begin{align} \text{even}\ + \text{odd} &= \text{length}\\ \text{even}\ = \text{odd} &= \text{count}\\ \therefore 2\text{count} &= \text{length} \end{align} $$

• You can just return <exp> rather than

  if <exp>:
      return True
  else:
      return False
  

• You don't need the first if n % 2 == 0: check.

def balanced(lst):
    n = len(lst)
    if n % 2 != 0:
        return False
    count = 0
    for item in lst:
        if item % 2 == 1:
            count += 1
    return 2 * count == n

• You can use sum and a comprehension to create count. If we build a list of counts then we can see how sum works with lists:

  counts = []
  for item in lst:
      if item % 2 == 1:
          counts.append(1)
  count = sum(counts)
  

  This should make sense as it's just totalling all the values. From here we can use some sugar to build a list comprehension. This would look like:

  counts = [
      1
      for item in lst
      if item % 2 == 1
  ]
  count = sum(counts)
  

  You should see that it builds the list with a lot less noise. Making code quicker to read and more minimalistic.

  From here we can merge them all into one line, and convert the list comprehension to an implicit generator expression.

  count = sum(1 for item in lst if item % 2 == 1)
  

• You can remove the if as item % 2 is either 1 or 0, and so summing will provide the count of odd numbers.

• I would prefer seeing items or values rather then lst

def balanced(items):
    if len(items) % 2 != 0:
        return False
    count = sum(i % 2 for i in items)
    return 2 * count == len(items)

If we remove your well thought out optimization, then we can put this on one line:

def balanced(items):
    return len(items) == 2 * sum(i % 2 for i in items)

Answer 4

Do not use recursion for simple use cases like this one (OP has asked about this in the original, unedited question)! It can be done simply, as shown below. First, a walkthrough:

A construct like

    if n % 2 != 0:
        return False
    if n % 2 == 0:

can be simplified by omitting the second if statement, since you return early anyway. This saves a whole level of indentation:

    if n % 2 != 0:
        return False
    count_1 = 0
    ...

If you did not return and thus exit but instead did something else, use an else clause to avoid repeating yourself, which might introduce subtle errors and bugs. Instead do:

   if n % 2 != 0:
       <something other than return>
   else:
       count_1 = 0

---

Further, this

    if count_1 == count_2:
        return True
    else:
        return False

can just be

return count_1 == count_2

---

In your code, you loop over the list manually. This can be replaced by (faster) list comprehension. In fact, it can be a one-liner altogether, while still being readable:

def balanced(lst):
    return len([number for number in lst if number % 2 == 0]) == len(lst) / 2

This works without your if n % 2 != 0 guard clause, because an uneven list length divided by 2 (len(lst) / 2) will never return an integer (gives float with non-zero decimal part), and therefore always compare unequal to the left side.

The left side is a list comprehesion that simply gets all even numbers in the sequence. It could also grab all uneven ones. This will always be an integer.

This solution is faster and reasonably Pythonic. It does not treat the special case of a list of odd length.

Keeping it speeds up the code however. The following is roughly 20% faster than the above one-liner:

from timeit import timeit

def balanced(lst):
    n = len(lst)
    if n % 2 != 0:
        return False
    return len([number for number in lst if number % 2 == 0]) == n / 2

def main():
    test_lists = [
        [5, 1, 0, 2],
        [5, 1, 0, 2, 11],
        [],
        [1, 2, 3, 5, 6, 8, 5, 9],
        [2, 4, 5, 7],
        [1, 2, 4, 4],
        [1, 2, 3],
        [1, 2],
        [1],
        [0],
        [1, 1, 1, 1],
        [1, 1, 2, 2],
        [1, 2, 3, 4, 5],
        # ["hello"], # error
    ]
    for test_list in test_lists:
        # print(balanced(test_list), test_list, sep=":\t")
        balanced(test_list)

print(timeit("main()", globals=globals()))

Uncommenting print(balanced(test_list), test_list, sep=":\t") and just running main() without timing, it prints:

True:   [5, 1, 0, 2]
False:  [5, 1, 0, 2, 11]
True:   []
False:  [1, 2, 3, 5, 6, 8, 5, 9]
True:   [2, 4, 5, 7]
False:  [1, 2, 4, 4]
False:  [1, 2, 3]
True:   [1, 2]
False:  [1]
False:  [0]
False:  [1, 1, 1, 1]
True:   [1, 1, 2, 2]
False:  [1, 2, 3, 4, 5]

Answer 5

I made a benchmark. The test data is a Python list with 1,000,000 numbers between 1 and 30 (inclusive). I've tested every answer that has been given so far:

0.044s mean time - balanced_alex_2
0.047s mean time - balanced_alex
0.050s mean time - balanced_peilonrayz
0.060s mean time - balanced_mark
0.061s mean time - balanced_delta
0.065s mean time - balanced_mti2935
0.066s mean time - balanced_kangalioo_expanded
0.154s mean time - balanced_kangalioo_compact
0.178s mean time - balanced_anonymous

Benchmark code

The top two answers by Mark and Peilonrayz carelessly traded readability in an attempt to gain speed - only somewhat successfully as you can see. Alex' answers dominate the benchmark instead.

My answers went all in on readability, while disregarding performance. You can see that even my answer is in the same ballpark as the optimized version from Alex.

Even Alex' code is not as fast as you can go, though. Changing the code to use a NumPy array yields a mean runtime of 0.011s for Numpy - 4x faster than the fastest Python answer.

Conclusion; if you need

• best performance and ok readability => Numpy
• ok performance and bad readability => Alex
• acceptable performance and best readability => kangalioo

Answer 6

This is a good candidate for list comprehensions.

Here is some proposed code (not the most compact but should be fairly easy to understand):

from typing import List

def is_even(number: int) -> bool:
    return (number % 2) == 0


def balanced(lst: List)-> bool:

    # list empty: return True by choice
    if len(lst) == 0:
        return True

    return len([item for item in lst if is_even(item)]) == len([item for item in lst if not is_even(item)])

# testing
lst1 = [1, 2, 3, 4, 5, 6]
print(f'List: {lst1} - balanced: {balanced(lst1)}')

---

For convenience I have defined an additional function is_even.

Logic: count the even numbers, do the same with odd numbers and if both sets have the same length, return True. I am not verifying that all items in the list are int...

Answer 7

There are general refactoring lessons to be learned here. First, if you exit in an if statement, you don't need what follows to be the opposite of that if, because you can only reach that lower code if the original condition is falsy [sic]. The advantage is later code is less deeply nested. Similarly, the ending simplifies. Never return True if something and False otherwise, just return that something (cast to a bool if necessary). This insight simplifies your original logic for balanced to

def balanced(lst):
    if len(lst) % 2 != 0: return False
    count_1 = 0
    count_2 = 0
    for item in lst:
        if item % 2 == 0: count_1 += 1
        if item % 2 != 0: count_2 += 1
    return count_1 == count_2

(Note the guard clause meant we no longer needed to cache what you called n.) While the remaining pair of if statements could be an if/else instead, at this point it's worth simplifying with the mathematical insight others mentioned:

def balanced(lst):
    if len(lst) % 2: return False
    evens_minus_odds = 0
    for item in lst:
        evens_minus_odds += 1 if item % 2 == 0 else -1
    return evens_minus_odds == 0

Suddenly, you can't help but make it declarative instead of imperative:

def balanced(lst):
    return len(lst) % 2 == 0 and sum(1 if item % 2 == 0 else -1 for item in lst) == 0

Which is basically what everyone else got. Well, not everyone even bothered including the first check: it saves time for odd-length lists, but that's premature optimization because it'd be neater still to write

def balanced(lst):
    return sum(1 if item % 2 == 0 else -1 for item in lst) == 0

(Incidentally, 1 if item % 2 == 0 else -1 could also be replaced with (-1) ** (item %2).)

What have we learned?

• Long imperative code is often crying out to become short declarative code;
• Refactoring what little you can at first will gradually give you new ideas;
• Boolean logic cries out for simplification. It just so happens your code had no bugs, but the anti-if campaign exists because many aren't so lucky. I'm a big advocate of making code more declarative, in part because it makes it harder to create, or at least miss, certain bugs.

Answer 8

A response to the answerers on here so far: if you want best performance, use a C extension. If you want readability, use this:

def balanced(lst):
    num_even = sum(item % 2 == 0 for item in lst)
    num_odd = sum(item % 2 == 1 for item in lst)
    return num_even == num_odd

This is readable AND compact AND probably decently fast. The only thing that might be hard-to-understand, especially for new Python programmers, is the sum(<generator>) construct. You can also expand that construct for better accessibility for new programmers:

def balanced(lst):
    num_even = 0
    num_odd = 0
    for number in lst:
        if number % 2 == 0: # even
            num_even += 1
        else: # odd
            num_odd += 1
    return num_even == num_odd

These code snippets are very concise and clear, in contrast to the currently most-upvoted answers:

The top answer right now uses a special tilt variable. That seems to me like a cryptic trick just for the purpose of using one less variable. Why? We have lots of variables to spare. It's hard-to-understand AND not compact AND probably not even faster than the naive solution.

The second top answer right now uses mathematical tricks to prove that you only need to count half of the numbers to do the checking. That person is probably a great mathematician. Please don't code like that, though. At least not without commenting your hard-to-understand intent.

The most important metric to keep in mind while coding, especially in a language like Python, is readability. Like 99% of your codebase won't ever be a performance issue - and if performance is not an issue, the top priority is readability (after correctness, of course).

Answer 9

collections.Counter

I'm surprised Counter() hasn't been mentioned yet. It's raison d'être is to count things. Using Counter() results in a short easy to read function:

from collections import Counter

def is_balanced(seq):
    '''determines if seq has equal numbers of odd/even items'''

    count = Counter(item % 2 for item in seq)

    return count[0] == count[1]

It's not the fastest of the alternatives, but the performance is probably acceptable.

Answer 10

Here's a compact way of doing it, without using any loops or if statements.

lst = [1,2,3,5,6,8,5,9,4,6]

def balanced(lst):
    return(sum(map(lambda x: x%2, lst))==0.5*len(lst))

print(balanced(lst))

The map function creates a new list consisting of 1's and 0's corresponding to each element in the input list. 1 means the corresponding element is odd, 0 means the corresponding element is even. Then, the sum function is used to add up all the elements in the resulting list from the map fucntion. This tells us the number of odd elements in the original list. The result of the sum function is then compared to half the number of elements in the original list. If the comparison is equal, this means that there are an equal number of odd and even elements in the original list.

Answer 11

There are some interesting ideas raised by this problem, guard clauses (or perhaps we should say short circuits) being one of them, we can extend

if len(lst) % 2 != 0: return False

with

if len(lst) == 0: return True

This raises the question (from the point of view of efficiency) which order should they go in? The answer depends on the expected data. If empty arrays are very common, we should test for that first, if they are never (or extremely rarely) going to occur we don't need the test.

Since we can't do a good design without some knowledge of the domain, suppose we have to test only ISBN 13s? In that case we can just write

return False

Another thing we can do is add a short circuit in the loop, something like:

length = len(list) 
for index, item in enumerate(list)
    if (length - index < abs(count) ) return False 
    count += ...

Again in most circumstances this is not worth the candle, but if we have billion digit ternary numbers the potential time saving would be considerable! (We might even decide to sort such an array with the smaller, and hence shorter numbers first.)