Interview question : Given two lists of different size, find a solution to have no more zeros in two lists, and the sum of the two becomes equal

Question

I wonder if someone has a solution for this problem : Given two lists of different size, find a solution to have no more zeros in two lists, and the sum of the two becomes equal.

Input : Two lists of size n,m >= 0 Output : The two new lists, if it is not possible return -1

Example : l1 = [1,2,0,0,4] l2 = [3,0,7] Returns : l3 = [1,2,2,2,4], l4 = [3,1,7]

We have sum(l3) = sum(l4) and no more zeros in both list

Answer 1

I assumed that the numbers replacing the 0s are integers between 1-9... otherwise infinite-many solutions.

Idea: sum(l1_new) == sum(l1_new) means that sum(l1)+o1 == sum(l2)+o2 where o1 and o2 are the integers made of the partitions of the 0s. The sums of the old and new lists are constant and by rearranging the equation we get a linear relationship o2 = s1 -s2 + o1. Both o1 and o2 are subject to constraints depending on the amount of 0s per list (boundaries).

Finally use combination with replacements in order to include cases such as 3 = 1+1+1 where 1... is repeated. If this condition is too relaxed use itertools.combinations.

from itertools import combinations_with_replacement


def c(l1, l2):
    L1, L2 = l1.copy(), l2.copy()

    s1, s2 = sum(l1), sum(l2)
    os1, os2 = l1.count(0), l2.count(0) # amount of zeros per list
    ds = s1-s2

    # boundaries - lower/upper
    lb1 = (os1 if os1 else 0)
    ub1 = (9*os1+1 if os1 else 1)
    lb2 = (os2 if os2 else 0)
    ub2 = (9*os2+1 if os2 else 1)
    
    # trivial partition - no zeros
    if os1 == os2 == 0:
        if s1 == s2:
            return l1, l2
        return -1
    
    # trivial partition - same amount of zeros
    if os1 == os2:
        if s1 == s2:
            return ([i if i else 1 for i in l1],
                    [i if i else 1 for i in l2])
        return -1

    # finding size of partition
    for o1 in range(lb1, ub1):
        o2 = ds + o1
        if lb2 <= o2 <= ub2:
            break
    else:
        return -1

    # partitioning of the integer
    po1 = next(c for c in combinations_with_replacement(range(1, 10), r=os1)
               if sum(c) == o1)
    po2 = next(c for c in combinations_with_replacement(range(1, 10), r=os2)
               if sum(c) == o2)

    # replacing the zeros
    for n in po1:
        L1[L1.index(0)] = n

    for n in po2:
        L2[L2.index(0)] = n

    return L1, L2

Here some tests

ls = [
    ([1,2,4], [7]), 
    ([1,2,4], [8]),
    ([1,6,9], [8, 8]),    
    ([1,0,6,9], [8, 0, 8]),    
    ([0, 1,6,9], [5, 8, 8]),    
    ([1,2,4], [7, 0]), 
    ([1,2,0,0,4], [3,0,7]),
    ([9,2,0,4], [7,0,7]),
    ([1,2,0,0,4], [3,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 7]),
    ([0, 0, 0], [0, 0, 0, 0]),
    ([0, 0, 0, 0], [9, 9, 9]),
]

for l1, l2 in ls:
    o  = c(l1, l2)
    print(f"{l1}, {l2} -> {o}")

Output

[1, 2, 4], [7] -> ([1, 2, 4], [7])
[1, 2, 4], [8] -> -1
[1, 6, 9], [8, 8] -> ([1, 6, 9], [8, 8])
[1, 0, 6, 9], [8, 0, 8] -> ([1, 1, 6, 9], [8, 1, 8])
[0, 1, 6, 9], [5, 8, 8] -> ([5, 1, 6, 9], [5, 8, 8])
[1, 2, 4], [7, 0] -> -1
[1, 2, 0, 0, 4], [3, 0, 7] -> ([1, 2, 1, 3, 4], [3, 1, 7])
[9, 2, 0, 4], [7, 0, 7] -> -1
[1, 2, 0, 0, 4], [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 7] -> -1
[0, 0, 0], [0, 0, 0, 0] -> ([1, 1, 2], [1, 1, 1, 1])
[0, 0, 0, 0], [9, 9, 9] -> ([1, 8, 9, 9], [9, 9, 9])