Java boolean-algorithm to check wheter number of digits is even

Question

I´m trying to write a recursive method that returns true, if the count of digits of n displayed as a binary number is even and false if it is odd. I don´t really get how I can count in a recursive method, if it returns a boolean.

I think part of the solution is, to check whether the number is a powers of 2:

static boolean isPowers2(long n) {
    if (n % 2 != 0) return false;
    if (n / 2 == 1) return true;
    return isPowers2(n / 2);
}

If the exponent is odd then the count of digits is even, if it is even then the count of digits is uneven. But I can not pass a value with my boolean function, right?

Some examples for what should be returned:

  // evenCount(0B0    ) is false
  // evenCount(0B1    ) is false
  // evenCount(0B10   ) is true
  // evenCount(0B11   ) is true
  // evenCount(0B100  ) is false
  // evenCount(0B111  ) is false
  // evenCount(0B1000 ) is true
  // evenCount(0B1010 ) is true
  // evenCount(0B10000) is false
  // evenCount(0B10110) istfalse

This is a question I failed on an algorithms test in university and I still can´t figure out how to solve it. I hope someone can give me a hint on how to solve this one...

@Nelfeal: How would you display 0? I would display with one digit, a "0". One digit is an odd number. — President James K. Polk
– President James K. Polk, Commented Jan 31, 2018 at 20:56

Eran · Accepted Answer · 2018-01-31 19:34:12Z

6

Checking if the input is a power of 2 is irrelevant. You should write a recursive method that removes one bit in each call.

A number has an even binary length if an only if it has an odd length if you remove one bit from it.

static boolean hasEvenLength(int n)
{
    if (n<2) { // single digit
        return false;
    }
    return !hasEvenLength(n/2);
}

This handles non-negative input. For negative numbers I can argue that you should always return true, since the most significant bit (the sign bit) is always set, so you can say the number has 32 binary digits.

Here's the output of the method for all numbers between 0 and 99:

0 0 false
1 1 false
2 10 true
3 11 true
4 100 false
5 101 false
6 110 false
7 111 false
8 1000 true
9 1001 true
10 1010 true
11 1011 true
12 1100 true
13 1101 true
14 1110 true
15 1111 true
16 10000 false
17 10001 false
18 10010 false
19 10011 false
20 10100 false
21 10101 false
22 10110 false
23 10111 false
24 11000 false
25 11001 false
26 11010 false
27 11011 false
28 11100 false
29 11101 false
30 11110 false
31 11111 false
32 100000 true
33 100001 true
34 100010 true
35 100011 true
36 100100 true
37 100101 true
38 100110 true
39 100111 true
40 101000 true
41 101001 true
42 101010 true
43 101011 true
44 101100 true
45 101101 true
46 101110 true
47 101111 true
48 110000 true
49 110001 true
50 110010 true
51 110011 true
52 110100 true
53 110101 true
54 110110 true
55 110111 true
56 111000 true
57 111001 true
58 111010 true
59 111011 true
60 111100 true
61 111101 true
62 111110 true
63 111111 true
64 1000000 false
65 1000001 false
66 1000010 false
67 1000011 false
68 1000100 false
69 1000101 false
70 1000110 false
71 1000111 false
72 1001000 false
73 1001001 false
74 1001010 false
75 1001011 false
76 1001100 false
77 1001101 false
78 1001110 false
79 1001111 false
80 1010000 false
81 1010001 false
82 1010010 false
83 1010011 false
84 1010100 false
85 1010101 false
86 1010110 false
87 1010111 false
88 1011000 false
89 1011001 false
90 1011010 false
91 1011011 false
92 1011100 false
93 1011101 false
94 1011110 false
95 1011111 false
96 1100000 false
97 1100001 false
98 1100010 false
99 1100011 false

edited Jan 31, 2018 at 19:34

answered Jan 31, 2018 at 19:24

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Jacob G. Over a year ago

Good answer! If you wanted to support negative numbers, I reckon you can check if Math.abs(n) < 2, and then use n >> 1 rather than n / 2.

Eran Over a year ago

@JacobG. Actually, I can argue that for negative numbers you should always return true, since the most significant bit is 1, so the number has 32 digits.

Jacob G. Over a year ago

That's true, assuming OP's intention wasn't to flip the meaning of 1 and 0 with negative numbers. Probably out of scope for the question anyway.

nicenoize Over a year ago

Wow thank you! The solution is much shorter than I thought... Just one more question: I get it that I have to remove one digit at a time. Where I´m still stuck is the recursive call. It means that I alternate between true and false each time when I remove a number, right?

Nelfeal · Accepted Answer · 2018-01-31 19:25:44Z

1

You don't need to count the digits, you just need to keep track of whether that count is odd or even.

boolean hasEvenDigitCount(long n) {
    if (n/2 == 0) { // handles both 1 and 0 as an even number of digits
        return false;
    }
    return !hasEvenDigitCount(n/2);
}

answered Jan 31, 2018 at 19:25

Nelfeal

13.3k1 gold badge23 silver badges42 bronze badges

Comments

user unknown · Accepted Answer · 2018-02-01 07:24:36Z

While the solutions by Nelfeal and Eran are fine, I like to mention a general way, while solving recursive problems, which is to carry the intermediate result as an additional parameter.

 def isEvenLength (n: Long) : Boolean = {

     def isEvenLength (n: Long, sofar: Boolean) : Boolean = {
         if (n < 2) sofar else isEvenLength (n/2, !sofar) 
     } 

     isEvenLength (n, false) 
 }

I don't think that inner functions have reached Java yet, so in Pseudo-Java, it would look more like this:

 static boolean isEvenLength (final long n, final boolean sofar) {
     if (n < 2) sofar else isEvenLength (n/2, !sofar);
 } 

 static boolean isEvenLength (final long n) {
     isEvenLength (n, false);
 }

So counting the length could be done by adding always one to sofar

 if (n < 2) sofar else isEvenLength (n/2, sofar+1)

With (hopefully) int as type for sofar.

user6874700 · Accepted Answer · 2018-02-01 13:13:59Z

0

As a hacker trick you can use this in java (not effective by speed):

static boolean hasEvenLength(int n) {
    return Long.toBinaryString(n).length() % 2 == 0;
}

answered Feb 1, 2018 at 13:13

user6874700

Collectives™ on Stack Overflow

Java boolean-algorithm to check wheter number of digits is even

4 Answers 4

4 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related