(num % 2) can result in 0, 1, and more? in C#

Question

I'm solving some algorithm test which is Collatz conjecture.

In short,

1-1. if the number is even, divide it by 2
1-2. if odd, multiply it by 3 and plus 1
2. repeat the same process 1(1-1 or 1-2), until the number become 1.

For example, 6 become 1, after 8 tries(6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1).

In the test, it should be ended in 500 tries and returns times of try. If it fails in 500 times, then returns -1.

Here's my code.

using System;

public class Program {

    public int Main(int num) {

        int answer = -1;
        int maxTry = 500;
        int count = 0;

        if (num == 1)
            return count;
        for (count = 0; count < maxTry; count++)
        {
            // 1-1
            if (num % 2 == 0)
            {
                num /= 2;
            }
            // 1-2
            else
            {
                num = num * 3 + 1;
            }

            if (num == 1)
            {
                answer = count + 1;
                break;
            }
        }

        Console.Write(answer);
        return answer;
    }
}

It was working quite well, before meet '626331'!. In explanation, 626331 can't be 1 in 500 times. But with my code, it return 488, which means it becomes 1 at 488 tries. When I printed process repeat by repeat, it looked working well.

After all attempts, found out that dividing was the problem.

I changed this

if (num % 2 == 0)
...
else
...

into

if (num % 2 == 0)
...
else if (num % 2 == 1)
...

Now every case works perfectly! But I don't have any clue for this situation.

It was online coding test and compile option was C# Mono C# Compiler 5.14.0.177

Your program overflows int range, which is `-2,147,483,648 to 2,147,483,647`. And your "fix" only works because now you can get 0, 1, or -1. Deal in long instead of int for proper behavior. — Andrei, Sep 09 '19 at 16:55
@PeterDeniho while it is kind of a duplicate in some sense, the core issue is not that mod negative is not covered in code, its the overflow itself. Thus I don't think this is a dupe of the linked question — Andrei, Sep 09 '19 at 16:55
During the loop, the variable `num` eventually gets the value `1069967879`. When this is multiplied by 3, the result is `3209903637`, which exceeds the range of the `int` type (max value of `2147483647`). The overflow results in the negative number `-1085063659`. Adding the `== 1` clause hides this fact, but doesn't really fix the problem, since the calculations are still not producing numbers within the expected range of the algorithm. See marked duplicate for more details about modulo arithmetic in C#. — Peter Duniho, Sep 09 '19 at 16:57
@Andrei: the post's title is _"(num % 2) can result in 0, 1, and more?"...obviously the main concern of the OP is that they are surprised that they got a result from `%` other than `0` or `1`. That said, I've also added a link to the duplicate post that addresses the range of values for `int` and other fundamental types in C#. — Peter Duniho, Sep 09 '19 at 16:58
@PeterDuniho, i see this point too now, thanks. But still, the core issue op didn't realize is overflow. Is it possible to attach two dupes here? — Andrei, Sep 09 '19 at 16:59

score 1 · Accepted Answer · answered Sep 09 '19 at 16:52

You're getting overflow, and once overflowed the result will be negative and num % 2 can return 0 or -1. The % operator in C# is the remainder operator, not the mathematical modulo operator. See Mod of negative number is melting my brain

You need to use a wider integer type (long) and enabling checked mode to detect overflow

(num % 2) can result in 0, 1, and more? in C#

1 Answers1