Python program to make a list even odd parity-CodePudding

Task: count the number of operations required to make an array's values alternate between even and odd.
Given: items = [6, 5, 9, 7, 3] (Example test case)
Operations we can do: make n number of operations: floor(item/2)

My code

def change(expected):
    return 1 if (expected == 0) else 0

def getMinimumOperations(items, expected):
    countOp = 0
    for i in items:
        if (int(i % 2 == 0) != expected):
            countOp  = 1
        expected = change(expected)
        
    return countOp
 
def minChangeToGetMinOp(items):
    minStack = [getMinimumOperations(items, 1), getMinimumOperations(items, 0)]
    return min(minStack)
 
if __name__ == "__main__":    
    items = [6, 5, 9, 7, 3]
    print(minChangeToGetMinOp(items))

ANS: 3

What I'm asking: A good approach to solve this

CodePudding user response：

Taking the comment that the division by 2 can be repeated multiple times on the same input number -- until its parity is as expected (or the number becomes 0 and the odd parity is required), the program would need an inner loop:

def getMinimumOperations(items, expected):
    countOp = 0
    for i in items:
        while i % 2 != expected:
            if not i:
                return float("inf")  # Not possible
            i //= 2
            countOp  = 1
        expected = 1 - expected
    return countOp
 
def minChangeToGetMinOp(items):
    return min(getMinimumOperations(items, 1), getMinimumOperations(items, 0))
 
if __name__ == "__main__":    
    items = [6, 5, 9, 7, 3]
    print(minChangeToGetMinOp(items))  # 3

CodePudding user response：

This seems like more of a math/logic problem than a Python problem.

To make a list's elements alternate between odd and even, either all the elements at even indices should be even and the rest odd, or all the elements at even indices should be odd and the rest even.

It appears you're not looking to change the order of elements, but to add or subtract one to make them comply.

So, to make the list comply, either you need to change all even elements at odd indices and all odd elements at even indices, or vice versa.

The answer therefore:

def needed_changes(xs):
    c = sum((i   n) % 2 for i, n in enumerate(xs))
    return min(c, len(xs) - c)


if __name__ == '__main__':
    xs = [6, 5, 9, 7, 3]
    print(needed_changes(xs))

Output:

The solution adds each element to its index, and then takes the mod 2 of it, so that each element becomes either 1 if the index or the value is odd, or 0 if both are odd, or both are even. As a result, the sum of those 1's will be the number of elements that need to be changed - but if that number is more than half, you could just change the rest of the elements instead, which is what the last lines decides.

Edit: From your comment it became clear that operations allowed are limited and the only operation allowed is x = floor(x / 2). This complicates the issue because this operation only results in an even outcome for every other two numbers. The pattern looks like this:

0 0  # 'even' to start with
1 0  # 'even' after 1 operation
2 1  # even to start with
3 1  # still odd after 1 op, after another 'even' (0)
4 2  # even to start with
5 2  # even after 1 op
6 3  # even to start with
7 3  # still odd after 2 ops, needs 3
8 4  # even to start with
..

So, each 4th number will be both odd, and its floor(x/2) will also be odd. If you apply the operation again, only half of those results will be even, etc.

Another way to look at the problem then: if a number's binary representation ends in a 0, it is even. If you take the floor(x/2) of a number, you're really just performing a "shift right" operation. So, if an number's binary representation has a 0 as the second least significant bit, performing the operation will make it even. And so on.

So, a solution using only that operation:

def needed_changes(xs):
    ns = []
    for x in xs:
        n = 0
        while x % 2:
            n, x = n   1, x >> 1
        ns.append(n)
    return min(sum(ns[0::2]), sum(ns[1::2]))

Or, if you don't like building a whole new list and want the solution to save space:

def needed_changes(xs):
    ns = [0, 0]
    for i, x in enumerate(xs):
        n = 0
        while x % 2:
            n, x = n   1, x >> 1
        ns[i % 2]  = n
    return min(ns)