Confusion of a code snippet in a interview

Question

I was asked, in an interview, what the below code does.

class Case {

    static int count1(int n) {
        if (n == 0) {
            return 0;
        }
        int m = n / 2;
        if (2 * m != n) {
            return 1 + count1(m);
        }
        return count1(m);
    }

    static int count0(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 0;
        }
        int m = n % 2;
        return count0((n - m) / 2) + 1 - m;
    }

    static boolean equivalent(int n, int m) {
        return ((count1(n) == count1(m)) && (count0(n) == count0(m)));
    }
}

First, I have to mention that the job is a data analyst internship and the only language required is Python and I'm a physics student so for me there is a huge difference between "//" and "/".

We first consider the function count1. I literally thought it was a trick question because int(2*m != n) was a trick question because it might cause a value error (my bad because I've been warned so many times about the difference between "//" and "/" in physics, I completely forgot that in other languages "7" can be used for integer division with a return value for floor division. So I stupidly thought it was a trick question and immediately pointed out that this would possibly give an error message and the if(2*m !=n) might be unnecessary.

Now what really confused me is count0, the second function. I simply pointed out the program doesn't solve anything, there is no pattern. The interviewer said it's supposed to return 0 or 1, but for it to return 0 or 1 then it's supposed to be count0((n-m/2+1-m), i.e. every term should be inside the parenthesis, right?

This interview took place yesterday evening. Should I write to my interviewer and tell him that even though failing to answer as to what the first function does is my fault but your second function may have a logic error? Of course in a nicer way.

PS: ChatGPT tells me this code is Java so I am adding the tag "java".

As I explained in the above text.

I realise i might have screwed up the first function, however here is the tested result tested using python:

# Implementing count0 function as described in the pseudocode
def count0(n):
    if n == 0:
        return 1
    if n == 1:
        return 0
    m = n % 2
    return count0((n - m) // 2) + 1 - m

# We will calculate the values of count0 for n = 0 to 20
results_count0 = {n: count0(n) for n in range(21)}

results_count0

results:

{0: 1, 1: 0, 2: 1, 3: 0, 4: 2, 5: 1, 6: 1, 7: 0, 8: 3, 9: 2, 10: 2, 11: 1, 12: 2, 13: 1, 14: 1, 15: 0, 16: 4, 17: 3, 18: 3, 19: 2, 20: 3}

Answer 1

If you look at some examples you can see the pattern:

input number	input number in binary	result of count0()	result of count1()
0	0	1	0
1	1	0	1
2	10	1	1
3	11	0	2
4	100	2	1
7	111	0	3
8	1000	3	1
10	1010	2	2

Answer 2

In case the sourcecode would be correct (so relates to the text in your question and not the foto of the piece of paper):

Case.count1(n) calculates the number of one-bits in the two's complement binary representation of n. This is equal to Integer.bitCount(n).

Case.count0(n) calculates the number of significant (!) zero bits in the two's complement binary representation of n. With significant I mean only zeros are counted that are on positions lower than the most significant one bit. This could also be calculated with Integer.bitCount((Integer.highestOneBit(n)<<1)-1-n).

The interviewer said it's supposed to return 0 or 1

These are not the only valid results of count0, just for an input of 0, the result is 1 and has to be handled separately, because input 0 doesn't contain any set bits, but still has 1 significant unset (zero) bit, and that is the least significant bit.

Case.equivalent(m, n) checks, if the number of one-bits and the number of zero-bits of the two given integers m and n are the same, so Case.equivalent(1, 2) would return true.

And relating to / vs. //: in Java, / can be used as division operator for integer and floating point numbers, while // marks the start of a line-comment, so that's no operator at all.

Answer 3

For people who like code (code is truth!), here is the betterized version.

This is Java-14+, it can probably be tried out on one of those free online Java consoles if you don't have the tools locally.

Also, for those interested in the details as revealed by the The On-Line Encyclopedia of Integer Sequences:

• count0() generates sequence A023416: Number of 0's in binary expansion of n.
• count1() generates sequence A000120: 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n)

package org.example;

public class Sequence {

    static int count1(int n) {
        if (n == 0) {
            return 0;
        }
        int m = n / 2;
        if (2 * m != n) {
            return 1 + count1(m);
        }
        return count1(m);
    }

    static int count1_better(int n) {
        if (n == 0) {
            return 0;
        }
        else {
            int leastSignificantBit = n%2;
            int shiftedRight = n/2; // or use n>>1, whatever
            return leastSignificantBit + count1_better(shiftedRight);
        }
    }

    static int count0(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 0;
        }
        int m = n % 2;
        return count0((n - m) / 2) + 1 - m;
    }

    static int count0_better(int n) {
        return switch (n) {
            case 0 -> 1;
            case 1 -> 0;
            default -> {
                int leastSignificantBit = n%2;
                int leastSignificantBitInverted = (1 - leastSignificantBit);
                // the original (n - m) / 2 is really for fractionals
                int shiftedRight = n/2; // or use n>>1, whatever
                yield leastSignificantBitInverted + count0_better(shiftedRight);
            }
        };
    }

    public static void main(String[] argv) throws Exception {
        final int limit = 10000;
        for (int i=0;i<limit;i++) {
            System.out.printf("%10s: zeros: %3d, ones: %3d\n",
                Integer.toBinaryString(i),
                count0_better(i),
                count1_better(i)
            );
            if (count1(i) != count1_better(i)) {
                throw new Exception("count1() and count1_better() differ at " + i);
            }
            if (count0(i) != count0_better(i)) {
                throw new Exception("count0() and count0_better() differ at " + i);
            }
        }
    }

}

And so:

         0: zeros:   1, ones:   0
         1: zeros:   0, ones:   1
        10: zeros:   1, ones:   1
        11: zeros:   0, ones:   2
       100: zeros:   2, ones:   1
       101: zeros:   1, ones:   2
       110: zeros:   1, ones:   2
       111: zeros:   0, ones:   3
      1000: zeros:   3, ones:   1
      1001: zeros:   2, ones:   2
...