Java logic algorithm for checking the number of digits

Question

I am trying to write a recursive method that returns true if the number of digits n displayed as a binary number is equal to false if it is odd. I really don't understand how I can calculate in a recursive method if it returns a boolean.

I think part of the solution is to check if the number has a value 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 number of digits is even, if it is equal, then the number of digits is uneven. But I can not pass the value with my boolean function, right?

Some examples of 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 that I failed in algorithm tests at the university, and I still cannot figure out how to solve it. Hope someone can give me a hint on how to solve this problem ...

Answer 1

Checking if input 2 is power does not matter. You must write a recursive method that removes one bit in each call.

A number has an even binary length, if 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 function handles non-negative input. For negative numbers, I can argue that you should always return true, since the most significant bit (sign bit) is always set, so you can say that the number has 32 bits.

Here's the method output 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 

Answer 2

You do not need to count the numbers, you just need to keep track of whether this account 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); } 

Answer 3

While the Nelfeal and Eran solutions are beautiful, I would like to mention a general method, solving recursive problems that should carry an 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 the internal functions have already reached Java, so in Pseudo-Java it would look 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, length counting can be done by always adding one to sofar

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

With (hopefully) int as type for sofar.

Answer 4

As a hacker trick, you can use this in java (inefficient in speed):

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