C++. Logical expression

Question

I am trying to solve the following task. Given an integer x, I want to compute 2 numbers (a and b) which are:

1. 1) divisible by 2 or 3 (e.g a % 2 == 0 or a % 3 == 0 )
2. 2) x = a + b

I wrote the following code, to find such a and b.

cin >> x;
if (x % 2 == 0) { 
     a = b = x / 2;
} else {
    a = x / 2;
    b = a + 1;
}
while((a % 3 !=0 || a % 2 != 0)  && (b % 2 != 0 || b % 3 != 0)) {
    a++;
    b--;
}

However it does not work. For example when x is 13, it prints out that a = 6 and b = 7. But 7 is not divisible by 2 or 3. What is the problem ?

Answer 1

Examine your continuation condition carefully (where n is some arbitrary integer, possibly different in each use so, for example a != 3n simply means that a is not a multiple of three). I'll show the process:

while((a % 3 != 0 || a % 2 != 0)  && (b % 2 != 0 || b % 3 != 0))
      ( a != 3n   OR  a != 2n  ) AND ( b != 2n   OR   b != 3n )
      (        a != 6n         ) AND (        b != 6n         )

It says: continue while both a is not a multiple of both two and three, and b is not a multiple of both two and three. In other words, it will only continue if both a and b are multiples of six. On the flip side of that, it will of course exit if either a or b is not a multiple of six.

Since an input value of 13 sets a = 6 and b = 7, the continuation case is false on the first iteration (seven is not a multiple of six).

Perhaps it would be better to rethink the way you figure out whether certain number combinations are valid^(a). For example (assuming the numbers have to be between 1 and N - 1 since, otherwise, your solution space is likely to be infinite), you could use something like:

#include <iostream>

int main() {
    // Get the number.

    int num;
    std::cout << "Number? ";
    std::cin >> num;

    // Check all i + j = n for 1 <= i,j < n.

    for (int i = 1, j = num - 1; i < j; ++i, --j) {
        // Disregard if either number not a multiple of 2 or 3.

        if ((i % 2) != 0 && (i % 3) != 0) continue;
        if ((j % 2) != 0 && (j % 3) != 0) continue;

        std::cout << num << " => " << i << ", " << j << "\n";
        return 0;
    }

    std::cout << num << " => no solution\n";
    return 0;
}

---

Note my use of i < j is the for continuation condition, this is assuming they have to be distinct numbers. If they're allowed to be the same number, change that to i <= j.

---

^(a) Using all of and, or, and not (even implicitly, by the reversal of continuation and exit conditions), is sometimes more trouble than it's worth since De Morgan's theorems tend to come into play:

_____     _   _
A ∩ B  ⇔  A ∪ B  : (not(A and B))  is  ((not A) or  (not B))
_____     _   _
A ∪ B  ⇔  A ∩ B  : (not(A or  B))  is  ((not A) and (not B))

In cases like that, code can become more readable if you break out the individual checks.

---

Interestingly, if you run that code with quite a few input values, you'll see the pattern that, if a solution exists, one of the numbers in that solution is always two or three.

That's because, other than the pathological cases of sums less than five (or less than four if the solution is allowed to have identical numbers):

• every even number 2n, n > 1 is the sum of 2 and 2n - 2, both multiples of two (2n - 2 = 2(n - 1)); and
• every odd number 2n + 1, n > 2 is the sum of 3 and 2n + 1 - 3, the first a multiple of three and the second a multiple of two (2n + 1 - 3 = 2n - 2 = 2(n - 1)).

So, in reality, no loop is required:

if (num < 5) { // 4 if allowing duplicates.
    std::cout << num << " => no solution\n";
} else {
    int first = (num % 2) == 0 ? 2 : 3;
    std::cout << num << " => " << first << ", " << (num - first) << "\n";
}

This actually gives a different result for some numbers, such as 17 = 2 + 15 = 3 + 14 but both solutions are still correct.