16
\$\begingroup\$

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()
\$\endgroup\$
3
  • \$\begingroup\$ I don't think this deserves its own answer, but I didn't see any others mention it: your code would be a lot more readable if you inserted a new line after logically grouped parts of your code, such as the end of functions. \$\endgroup\$ May 20, 2020 at 6:46
  • 4
    \$\begingroup\$ A lot of people are trying to "improve" your code be trading readability for small gains in performance. I want to tell you - please don't think that that is what your Python code should look like. Your code should be first of all readable. IF and only IF that part of your codebase turns out to be a bottleneck, ONLY THEN optimize it! Premature optimization is the root of all evil. \$\endgroup\$
    – kangalio
    May 21, 2020 at 14:24
  • \$\begingroup\$ This question inspired Check if an array (or equivalent) has the same number of odd and even numbers - Code Golf Edition! - various languages, smallest code challenge \$\endgroup\$ May 23, 2020 at 0:42

11 Answers 11

24
\$\begingroup\$

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
\$\endgroup\$
21
  • 2
    \$\begingroup\$ Indeed. I wrote tilt += 1 - 2 * (item % 2), which is shorter but probably less readble. \$\endgroup\$ May 19, 2020 at 22:53
  • 1
    \$\begingroup\$ @EricDuminil definitely less readable. I considered item & 1 but that would have been even worse. The whole function could be condensed to one line: return sum(1 - 2 * (item & 1) for item in lst) == 0. \$\endgroup\$ May 19, 2020 at 23:02
  • 1
    \$\begingroup\$ I look at your code and I see that it is more elegant than the original code. But still, I can glance over OPs code and know what it does, booting up only the dumbest part of my brain. This submission gives me just that tiny bit of extra resistance :-/ \$\endgroup\$
    – epa095
    May 20, 2020 at 11:48
  • 3
    \$\begingroup\$ @MarkRansom Its shorter, not simpler (although I do agree that "simple" is a subjective notion). If I show you a pile of apples and oranges and asks you if there are equally many of them, what do you do? I would count oranges and apples respectibly and compare. I would not keep a single variable (tilt) which I let go above and below zero until I finally check if it is zero. It takes just that tiny bit of extra mental effort to handle the tilt variable, which can be both negative and positive, and the fact that it is zero iff the two amounts are equal. \$\endgroup\$
    – epa095
    May 20, 2020 at 19:58
  • 3
    \$\begingroup\$ @kangalioo I'm afraid I must disagree, this form is more readable to me than the original in the question. It distills the concept of "balance" down to its essence. Imagine a balance scale, and you're dropping items on to one side or the other depending on if they're odd or even. You will never know the exact count on either side of the scale, nor will you care. \$\endgroup\$ May 21, 2020 at 15:28
12
\$\begingroup\$

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.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ I like this. Its less clever than many others, but it retains a property I liked about the original code; it takes me a single glance over it to know exactly what it does, while removing some of the obvious eye-sores. \$\endgroup\$
    – epa095
    May 20, 2020 at 11:41
  • 3
    \$\begingroup\$ @epa095 I feel like its a common issues with python. A lot of things can be turned into nifty one-liners, but it defeats one of the purposes of the language: it's designed to be readable. \$\endgroup\$
    – gazoh
    May 20, 2020 at 13:05
  • 2
    \$\begingroup\$ @epa095 - In my opinion, 'Cleverness' in code is a drawback, not a benefit. Simplicity and Readability are the things that really matter 99% of the time. \$\endgroup\$
    – Kevin
    May 21, 2020 at 20:15
10
\$\begingroup\$
  • 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)
\$\endgroup\$
11
  • \$\begingroup\$ What is the content in this new sum function "sum(.....)" called? Does this function come under advanced courses of python? \$\endgroup\$ May 19, 2020 at 14:24
  • \$\begingroup\$ @UncalledAstronomer I do not know what you mean by context. It's a built-in function. I have not followed any Python courses and so I do not know what 'level' it is. However I personally would say it's either beginner/basic or not included in your course. \$\endgroup\$
    – Peilonrayz
    May 19, 2020 at 14:27
  • 3
    \$\begingroup\$ @UncalledAstronomer it's technically a generator expression. If you look them up, their content is the same as list comprehensions, but they're surrounded by parentheses. If they're used as the only argument to a function, like what's going on here in the call to sum, then instead of having two sets of parentheses (one for the function call, one for the generator expression), you can discard the redundant parenthesis and get what you see above. \$\endgroup\$
    – scnerd
    May 19, 2020 at 15:11
  • 1
    \$\begingroup\$ @EricDuminil B-but, mine is one pass! ;) \$\endgroup\$
    – Peilonrayz
    May 19, 2020 at 22:59
  • \$\begingroup\$ In general an either-or per-element classification should be optimized for count one thing and calculate the other from y = length - x after the loop. This optimization isn't limited to cases where you're looking for balanced. E.g. if you just want to return both odd and even counts you should still only count one in the loop (or list comprehension). But yes, optimizing it to 2*count_odd == len is good. \$\endgroup\$ May 21, 2020 at 2:05
7
\$\begingroup\$

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]
\$\endgroup\$
4
  • \$\begingroup\$ @Peilonrayz Thank you, I am well aware! In the original question, OP had asked for a recursive solution. \$\endgroup\$
    – Alex Povel
    May 19, 2020 at 14:56
  • \$\begingroup\$ Indeed they did in the original title. Might I suggest you edit your answer to clarify that for future readers. \$\endgroup\$
    – Peilonrayz
    May 19, 2020 at 15:00
  • 2
    \$\begingroup\$ I benchmarked the answers and your code is the fastest of them all! 10% faster even than Peilonrayz' answer which heavily traded readability for performance \$\endgroup\$
    – kangalio
    May 21, 2020 at 14:10
  • \$\begingroup\$ @kangalioo Interesting, thanks for putting it together. I guess that is all down to our highly optimized lord and savior, list comprehensions. \$\endgroup\$
    – Alex Povel
    May 22, 2020 at 12:52
6
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ “The top two answers by Mark and Peilonrayz carelessly traded readability in an attempt to gain speed” — That’s explicitly not what Mark’s doing. \$\endgroup\$ May 22, 2020 at 7:32
3
\$\begingroup\$

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...

\$\endgroup\$
1
  • 1
    \$\begingroup\$ As a note, this makes two full lists, whereas the filtering conditions for the lists are mutually exclusive. That means we could omit one of the two (if a number is not even, it is automatically uneven) and still reach the same result. That saves a lot of work. \$\endgroup\$
    – Alex Povel
    May 22, 2020 at 12:57
3
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ Hmm you may have gone slightly overboard swinging the axe now; but it’’s definitely a good, concise answer. \$\endgroup\$ May 22, 2020 at 8:19
2
\$\begingroup\$

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).

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ map and lambda (for filtering) are often better replaced by (list) comprehension, which is usually found to be more readable and often faster (when passing lambda that is). map and lambda, among other things, were even supposed to be removed for Python 3. So they work, but aren't "pythonic", which is not entirely objective, of course. \$\endgroup\$
    – Alex Povel
    May 20, 2020 at 7:06
  • 2
    \$\begingroup\$ In this case, using sum(map(lambda x: x%2 or -1, lst)) might be nicer (no float comparison and tells which and how many wrong elements there are). If one wants a bool, return not bool() of the above will work. \$\endgroup\$
    – NichtJens
    May 20, 2020 at 9:38
  • 1
    \$\begingroup\$ Map is discouraged by Guido and deprecated by Google. Additionally the Pythonic solution to this is comprehensions as explained by Alex Povel. This is bad advice, it still has a loop too... \$\endgroup\$
    – Peilonrayz
    May 20, 2020 at 10:15
  • 1
    \$\begingroup\$ @Peilonrayz It’s worth noting that the Google style guide explicitly says the usage map(f, seq) is OK. Only map(lambda …, seq) is discouraged. \$\endgroup\$ May 22, 2020 at 7:30
  • \$\begingroup\$ @KonradRudolph Indeed it does say something like that. I'm not sure it applies here as even if you were to remove the lambda I'm not sure the author would be happy seeing f = 2..__rmod__ :) \$\endgroup\$
    – Peilonrayz
    May 22, 2020 at 12:27
1
\$\begingroup\$

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.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.