6
\$\begingroup\$

As already written in the title I want to count the numbers in the range (x+1, y) where x and y are integers, in which the sum of the digits in odd places have the same parity of the ones in even places. I made this code:

def findIntegers(x, y):
    count = 0    
    for k in range(int(x)+1, int(y)+1):
        odd_sum = 0
        even_sum = 0
        k = str(k)
        odd_sum += sum([int(k[i]) for i in range(1, len(k), 2) if i % 2 == 1])
        even_sum += sum([int(k[i]) for i in range(0, len(k), 2) if i % 2 == 0])
        if (odd_sum % 2) == (even_sum % 2):
            count += 1            
    return count

The code works but for very big range it's very slow. How can I improve my code?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ And clarify the task; is x excluded from the range and y included? \$\endgroup\$ Nov 26 '21 at 11:23
  • \$\begingroup\$ "even places have same parity as odd places" reduces to very simple rule: the mod 2 sum of all the digits equals 0. No need to break it into two pieces. Also, if you just look at some example ranges you'll notice a very simple pattern to the count, so you don't need to actually run through the values. \$\endgroup\$ Nov 27 '21 at 2:45
5
\$\begingroup\$

First some code simplifications and other adjustments. (1) Your sum calculations don't need the conditional tests, because the ranges already ensure compliance. (2) They also don't need to be wrapped in a []. (3) Even better, if you switch from ranges to slices, you don't need to loop with in the sum calculations: just give a slice directly to sum(). In order to do that, you can perform string-to-int conversion in one place, before summing. (4) Because bool is a subclass of int, your count-incrementing code does not require conditional logic. (5) This function is difficult to describe and name compactly, but your current name is especially vague. Here's a possible renaming. (6) Finally, and this is done purely to simplify the rest of the discussion, I have modified the function to do the counting over an inclusive range.

def n_parity_balanced_integers(x, y):
    count = 0
    for number in range(x, y + 1):
        digits = tuple(map(int, str(number)))
        count += sum(digits[0::2]) % 2 == sum(digits[1::2]) % 2
    return count

Such edits improve the code, but they do not significantly affect the algorithm's speed. It's still a brute-force solution. The key to making further progress is to find a pattern that can be used to radically reduce the needed computation. One way to find these patterns is to experiment with the data. For example:

# A brief experiment.
checks = [
    (0, 9),
    (0, 99),
    (0, 999),
    (0, 9999),
    (10, 19),
    (20, 29),
    (10, 39),
]
for lower, upper in checks:
    print(f'{lower}-{upper}:', n_parity_balanced_integers(lower, upper))

# Output
0-9: 5
0-99: 50
0-999: 500
0-9999: 5000
10-19: 5
20-29: 5
10-39: 15

In other words, over any inclusive range spanning an entire power-of-ten's worth of numbers (or any multiple of that, such as 10-39), you can instantly compute the answer without iterating over every discrete number in the range. So the trick to this problem is to start with the full range, decompose it into subcomponents that can be computed instantly, and then brute-force any straggling bits. Give that a shot a see what you come up with.

\$\endgroup\$
3
\$\begingroup\$

Use type hints and unit tests

They are simple and make your code better.

Some improvements and pythonification

odd_sum and even_sum are initialized with zeroes before adding to them, so you can simply initialize them instead of adding:

for k in range(int(x)+1, int(y)+1):
    k = str(k)
    odd_sum = ...
    even_sum = ...

range with step 2 already omits evens or odds, so the if part isn't needed:

odd_sum = sum([int(k[i]) for i in range(1, len(k), 2)])

Moreover, you don't need the index i, you need only digits, so you can use slice instead of range:

odd_sum = sum(int(digit) for digit in k[1::2])

Better algorithm

If a number x has this property and adding 1 doesn't cause change in other digits except the last, x+1 will don't have this property, x+2 will have it once again etc. So among every 10 consecutive numbers staring with ...0 there will be 5 fitting numbers. You should check only starting and ending numbers, the half of the rest will do in any case.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Sorry, I'm sure that this is correct but I don't understand the last sentence You should check only starting and ending numbers, the half of the rest will do in any case. Do you mean if a=10 andb=100 I should check only a and b or do you mean for every number I should check the starting and the ending digit? \$\endgroup\$
    – DarkSkull
    Nov 26 '21 at 13:18
  • \$\begingroup\$ Only 10 and 100. The answer should be somewhere around (100-10)/2 depending on whether 10 and 100 fit the condition (in fact, it's exactly 45). \$\endgroup\$ Nov 26 '21 at 14:13
  • \$\begingroup\$ one last question @PavloSlavynskyy, how did you come up to the solution? Is there some related problem? \$\endgroup\$
    – DarkSkull
    Nov 26 '21 at 18:18
  • \$\begingroup\$ Thnx @AJNeufeld, fixed. 2DarkSkull No, just an observation. \$\endgroup\$ Nov 26 '21 at 21:47
1
\$\begingroup\$

By making a few observations an O(1) algorithm can be devised. First note that the statement

the sum of the digits in odd places have the same parity of the ones in even places

is equivalent to the statement that the sum of all the digits equals 0 mod 2. Equivalently, the XOR of the low-order bit of all the digits equals 0. The following function implements this

from typing import Sequence

def is_same_parity(digits: Sequence[int]) -> bool:
    return sum(digits) % 2 == 0

The next observation is actually the only important one in term of algorithmic complexity. Every sequence of 10 contiguous integers that starts with a multiple of 10 always has exactly 5 values whose (base 10) digits sum to 0 mod 2. If the first value of the sub sequence a (a mod 10 == 0) has digits that sum to 0 then the five values are a, a+2, a+4, a+6, and a+8. Otherwise, the values are a+1, a+3,a+5, a+7, and a+9.

We can therefore break our range into three pieces, a beginning piece that goes to the next multiple of 10, a trailing piece that goes from the last multiple of 10 to the end, and a third piece that is everything between the first and last multiple of 10 in the sequence.

The following code implements this idea

def find_integers_helper(x: int, y: int) -> int:
    """
    Counts integers whose base10 digits sum to 0 mod 2 in the range
    x <= z < y
    Break into 3 separate ranges:
        1) x <= z1 < y1, where y1 = 10 * ceiling(x / 10), and
        2) y1 <= z2 < y2, where y2 = 10 * floor(y / 10), and
        3) y2 <= z3 < y
    :param x:
    :param y:
    :return:
    """
    
    y1, y2 = 10 * ceil_div(x, 10), 10 * floor_div(y, 10)
    c1 = sum(1 for z1 in range(x, y1) if is_same_parity(to_digits(z1)))
    c2 = (y2 - y1) // 2
    c3 = sum(1 for z3 in range(y2, y) if is_same_parity(to_digits(z3)))

    return c1 + c2 + c3

# some simple helper functions

def ceil_div(n: int, d: int) -> int:
    return (n + d - 1) // d


def floor_div(n: int, d: int) -> int:
    return n // d


def to_digits(x: int) -> tuple[int]:
    return tuple(int(d) for d in str(x))


When I reason about ranges I have a strong preference to think about ranges that look like x <= y < z. It's just the way I've done it my whole life. Your code wants a slightly different range, so your method can call my method with a slight adjustment:

def find_integers(x: int, y: int) -> int:
    return find_integers_helper(x + 1, y + 1)
\$\endgroup\$
2
  • \$\begingroup\$ to_digits is not defined \$\endgroup\$
    – DarkSkull
    Nov 27 '21 at 16:07
  • \$\begingroup\$ @DarkSkull: Whoops! \$\endgroup\$ Nov 27 '21 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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