check if n numbers are all odd or even using - + * operations only

Question

is there a way to check N numbers if they are all odd or even without using mod function %??? ,i can only use - + * functions.

Answer 1

So you can use addition, subtraction, multiplication, and comparisons. I'll also assume you can define functions, and your goal is to define two functions:

• The evenList function takes a list of numbers and returns true iff (if-and-only-if) the list contains only even numbers.
• The oddList function takes a list of numbers and returns true iff the list contains only odd numbers.

First let's define an even function that takes a single number and returns true iff the input is even:

even(i) = if (i == 0) true
          else if (i == 1) false
          else if (i > 1) even(i - 2)
          else /* i < 0 */ even(i + 2)

We can define an odd function in terms of even:

odd(i) = even(i+1)

We could then just define evenList recursively too:

evenList(nil) = true
eventList(x : xs) = even(x) & evenList(xs)

(I'm using x : xs to mean a list whose first element is x and whose remainder is xs. I'm using nil to mean an empty list.)

But maybe you're not allow to use a boolean & operator. What can we do instead?

Consider multiplying two numbers, i and j. What parity is the result, based on the parity of i and j? (Parity means oddness or evenness.)

• even(i) & even(j) -> even(i*j)
• even(i) & odd(j) -> even(i*j)
• odd(i) & even(j) -> even(i*j)
• odd(i) & odd(j) -> odd(i*j)

(I'm using -> to means “implies”.) In other words, i*j is odd iff i is odd and j is odd.

So, if you multiply all of your input numbers together and the product is odd, then all of the inputs are odd. So we'll define a product function:

product(nil) = 1
product(x : xs) = x * product(xs)

And then we can define oddList like this:

oddList(xs) = odd(product(xs))

But how to know if all of the inputs are even? Even a single even input makes the product even.

The trick is to reverse the parity of all the inputs, and then reverse the parity of the result. You can reverse the parity by adding or subtracting one. Let i1 = i + 1 and j1 = j + 1. Then:

• even(i) & even(j) -> odd(i1) & odd(j1) -> odd(i1 * j1) -> even(i1 * j1 + 1)
• even(i) & odd(j) -> odd(i1) & even(j1) -> even(i1 * j1) -> odd(i1 * j1 + 1)
• odd(i) & even(j) -> even(i1) & odd(j1) -> even(i1 * j1) -> odd(i1 * j1 + 1)
• odd(i) & odd(j) -> even(i1) & even(j1) -> even(i1 * j1) -> odd(i1 * j1 + 1)

In other words, (i+1) * (j+1) + 1 is even if and only if i is even and j is even.

So, let's define a product1 function that returns the product of all of its inputs, each incremented by 1 first:

product1(nil) = 1
product1(x : xs) = (x + 1) * product1(xs)

Then we can define evenList like this:

evenList(xs) = even(1 + product1(xs))