>>14306640I assume the variables are odd. First, note that run time in terms of n, does not make much sense, since the input can be arbitrarily long even with just 1 variable. So I will assume the input is in normal form: sum of mononials of form c*x1^a1*x2^a2*...*xk^AK without repetitions of variables. Let there be m terms in the input. Now, if the the sum is odd, then an odd numer of terms are odd. A term is odd, if its constant and all its variables in it are odd. So, the powers do not matter (just whether they are 0 or > 0) and the values do not matter (just whether they are odd or even). So we can remove terms with even constants, rewrite terms as just sets of variables, remove terms which appear an even number of times and merge terms which appear an odd number of times. Note that if the constant term is odd, this is trivial, as we just assign even numbers to all variables, so we can assume it is even and remove it. Finally, we show that as long as there are terms left, there is a solution. Find a least term (least by set inclusion) and set all its variables to odd numbers. Then set all other variables to even numbers. Since the chosen term is a least one, every other term has at least one even variable. Therefore, we have exactly one odd term and thus the sum is odd. The complexity is something like O(mn log (mn)) (depends on your exact computation model).
