9
\$\begingroup\$

I was doing a few basic Java recursion problems to refresh my memory with recursion (honestly never had to use it in a long, LONG, time), along with using it as a useful way to prepare for any possible interviews for entry level positions. I came upon this problem on codingbat.com:

Given a non-negative int n, compute recursively (no loops) the count of the occurrences of 8 as a digit, except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4. Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).

  • count8(8) → 1
  • count8(818) → 2
  • count8(8818) → 4

My solution, which was all correct for all the test cases they had is as follows:

public int count8(int n) {
  if(n == 0) {
    return 0;
  } else {

    int count = (n % 10 == 8)? 1: 0;

    //This is testing for adjacent 8s. 
    if(count == 1) {
      int tempN = n;
      tempN = tempN / 10;
      count = (tempN % 10 == 8) ? 2 : 1;
    }

    n = n/10;
    return count + count8(n);
  }
}

I was wondering if anyone could critique this solution, and let me know if this is the best approach, or if there is a better way. I am not a big fan of the if(count == 1) that I created, but that was the only way I could think of to test the presence of an 8 to the left of the current one.

\$\endgroup\$
11
\$\begingroup\$
  if(n == 0) {
    return 0;
  } else {  

You can omit the else here, because if n == 0 it will never be reached.


The hardcoded 8 is hurting my eyes a little bit. It would be better to pass it to the method as a parameter. In this way the magic number 8 would disappear. In addition the methods name wouldn't look that funny and the comment could be removed as well.


By just declaring int count = 0; and placing the (n % 10 == 8) as the if condition you would get rid the unwanted if(count == 1).


n = n/10; you should let your variables and operators some space to breathe. n = n / 10; is much more readable.


You could introduce a int getRightMostDigit(int) method to make the intend of % 10 more clear.


Implementing the mentioned points leads to

public int count(int n, int digitToCount) {
    if (n == 0) {
        if(digitToCount == 0) {
            return 1;
        }
        return 0;
    } 

    int count = 0;

    if (getRightMostDigit(n) == digitToCount) {
      int tempN = n;
      tempN = tempN / 10;
      count = (getRightMostDigit(tempN) == digitToCount) ? 2 : 1;
    }

    n = n / 10;

    if (n == 0 && digitToCount == 0) { // fix of the fix
        return count;
    }
    return count + count(n, digitToCount);

}
private int getRightMostDigit(int number) {
    return number % 10;
}

@Taemyr has found a bug in my answer:

Fix for the n==0, digitToCount==0 case introduce new bug. n==1, digitToCount==0 now returns 1.

This can be fixed like in the code above.

\$\endgroup\$
  • 4
    \$\begingroup\$ tempN = n is redundant. In fact, I'd do just count = getRightMostDigit(n / 10) == digitToCount ? 2 : 1. Maybe getRightMostDigitcould be private boolean lastDigitIs(int number, int digit)? \$\endgroup\$ – JollyJoker Jan 23 '17 at 9:42
  • \$\begingroup\$ About tempN = n I have thought the same, but decided to leave something for other answerers. You should post it as an answer yourself and get my +1 \$\endgroup\$ – Heslacher Jan 23 '17 at 9:45
  • 2
    \$\begingroup\$ This is wrong when n == 0 and digitToCount == 0. \$\endgroup\$ – Alex Reinking Jan 23 '17 at 11:26
  • \$\begingroup\$ @AlexReinking you are right. Updated answer. \$\endgroup\$ – Heslacher Jan 23 '17 at 11:29
  • 1
    \$\begingroup\$ @Heslacher Could do return digitToCount == 0 ? 1 : 0 \$\endgroup\$ – JollyJoker Jan 23 '17 at 12:04
12
\$\begingroup\$

Another approach is to let the recursive method know if the previous digit was an eight.

public int count8(int n) {
  return count8(n,false)
}

public int count8(int n, boolean lastDigitWasMatch) {
  if(n == 0) {
    return 0;
  } else {

    boolean match = (n % 10 == 8);
    int count = match?(lastDigitWasMatch?2:1):0;
    return count+count8(n/10,match);
  }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Exactly - the main problem with the code is that recursion is done halfway. There should be no need to peek for the next iteration's result when coding recursively. \$\endgroup\$ – Mikuz Jan 24 '17 at 15:45
6
\$\begingroup\$

I like Heslacher's answer, but I would not divide twice the number. I would just store the divided number for later use:

public int count(int n, int digitToCount) {
    if(n == 0) {
        return 0;
    } 

    int count = 0;
    int nDiv10 = n / 10;

    if(getRightMostDigit(n) == digitToCount) {
      count = (getRightMostDigit(nDiv10) == digitToCount) ? 2 : 1;
    }

    return count + count(nDiv10, digitToCount);

}
private int getRightMostDigit(int number) {
    return number % 10;
}

shorter (saves one write access), but maybe not as clear:

    int count = (getRightMostDigit(n) != digitToCount) ? 0 : ((getRightMostDigit(nDiv10) == digitToCount) ? 2 : 1);

Note: There is a bug: count(0, 0) should return 1...

\$\endgroup\$
  • \$\begingroup\$ lol, you're the only one to notice the 0,0 bug so far :) \$\endgroup\$ – JollyJoker Jan 23 '17 at 10:17
3
\$\begingroup\$

If you absolutely have to write this method recursively (see below), then the clearest, most readable, and most efficient way of doing so is the following:

public int count8_worker(int n, boolean lastWasEight)
{
    if (n == 0)
    {
        return 0;
    }

    boolean isEight = ((n % 10) == 8);
    n /= 10;
    return (isEight ? (lastWasEight ? 2 : 1) : 0) + count8_worker(n, isEight);
}

public int count8(int n)
{
    return count8_worker(n, false);
}

Giving credit where credit is due, this is a bit of a riff on Taemyr's solution in that it uses a Boolean variable to track whether or not the last digit processed was an 8, which I believe is more elegant than your original if(count==1) approach.

While I certainly wouldn't make an issue of it in a code review, I don't think that defining a getRightMostDigit (as suggested by Heslacher and others) is terribly important in terms of readability. Unless you need it for reuse (and remember, YAGNI), the logic is sufficiently short and obvious that it can be written on the other side of an assignment operator to an appropriately-named variable.

The repeated use of the conditional operator here is the only thing that detracts from the code's readability, and that's mainly because Java does not allow a Boolean value to be implicitly converted into an integer. The equivalent C code would be slightly easier to read:

return (isEight ? (lastWasEight + 1) : 0) + count8_worker(n, isEight);

What makes this maximally efficient is that we're only doing each operation once—each time through the loop, there is only one modulo, one division, and one comparison. Because they are back-to-back, a smart JIT compiler will fold the n % 10 and n /= 10 into a single divide instruction, which is by far the slowest instruction of the bunch. In fact, a really smart JIT compiler won't emit a divide instruction at all—at least, not when targeting x86. Rather, it will use a series of bit-twiddling and multiply-by-constant instructions to achieve the same effect but much more quickly.

Also, the use of these ternary conditional operators allows the JIT compiler to produce branchless code, which will be faster on balance, since the inputs are unpredictable, and mispredicted branches are slow. The alternative way of writing the code, used by some of the other answers, introduces branches that are extremely unlikely to be optimized out by the JIT compiler, essentially serving as performance landmines.

That said, if you actually care about performance, you would not write this recursively. I know, I know—the problem asked you to write a recursive routine, so that's what you did. That's great; computer science people love their recursion because it's theoretically elegant and theoretically as fast as iterative routines. In practice, though, it is neither. You had a difficult time proving to yourself that your recursive implementation was correct, and the way I read the question, you're still not completely confident. You relied on the few test cases that were provided, without being certain that there are no edge cases for which your code will return the incorrect result.

There's no valid reason why something like this would need to be implemented recursively, so I believe that a good programmer would question that part of the assignment and offer this iterative routine as an alternative:

int count8_iteratively(int n)
{
    int     count        = 0;
    boolean lastWasEight = false;
    while (n != 0)
    {
        boolean isEight = ((n % 10) == 8);
        n /= 10;
        count += isEight ? (lastWasEight ? 2 : 1) : 0;
        lastWasEight = isEight;
    }
    return count;
}

Not only is this easier to read, understand, and prove correct (in my opinion), it is objectively faster because it results in the generation of vastly more efficient code—and less of it, which is a win both in terms of caching and time-to-JIT.

Although an extremely smart ahead-of-time C++ compiler might (Clang does, for example, but not GCC, ICC, or MSVC), a Java JIT compiler will not inline the recursive method and turn it into iterative code. Java doesn't even do tail-recursion, so it certainly won't transform this into a loop. Frankly, the language is an iterative one, and so this is the style that programmers should follow. There is a good reason why you haven't had to use recursion in a long time. :-)

\$\endgroup\$
  • \$\begingroup\$ One non-recursive solution would be a for(char c : (""+n).toCharArray()) \$\endgroup\$ – JollyJoker Jan 24 '17 at 8:56
  • \$\begingroup\$ An extremely slow non-recursive solution. What would be the advantage of that over the code I posted? @jolly \$\endgroup\$ – Cody Gray Jan 24 '17 at 9:00
  • 1
    \$\begingroup\$ Feel free to add that as a new answer, @jolly. I think it's a terrible solution. The problem is about numbers, so it makes very little sense to convert the input to an entirely different domain (a string) and manipulate it that way. That only makes sense if there is a performance improvement to be had, but in this case, it's a massive pessimization. Furthermore, I don't agree that c == '8' is any more readable than n % 10 == 8. They are both obviously comparing something to 8. If you don't know what the modulo operation does, you probably shouldn't be touching the code. \$\endgroup\$ – Cody Gray Jan 24 '17 at 9:15
  • 2
    \$\begingroup\$ Thanks for clarifying that, @David! I fixed the code in the answer. I would have assumed it was like C#, where these type names were just aliases of each other. That Boolean is a nullable object is kind of a surprise—I see that as a huge design flaw. \$\endgroup\$ – Cody Gray Jan 24 '17 at 11:50
  • 1
    \$\begingroup\$ Thank you for explaining the performance aspect of the code, and I certainly prefer your approach to the count == 1 that I had. I never thought of creating a boolean and passing it as a another function. Certainly lots to learn. And I do agree, many of the recursion problems presented there make me think iteration is vastly easier. I know a lot of the latter ones deal with string and array manipulation, somewhat disgustingly the signature given passes in an index as well. Much easier to just do a for-loop. \$\endgroup\$ – SomeStudent Jan 24 '17 at 18:30
2
\$\begingroup\$

Thinking a bit on how I'd change @Heslacher's solution, I'd say the main issue to consider is where you want to insert named variables or methods for readability. Just to put the "human readable words" in completely different places;

public int count(int n, int digit) {
    if(n == 0) {
        return 0;
    }
    boolean last = n % 10 == digit;
    boolean secondLast = n / 10 % 10 == digit;
    int count = last ? secondLast ? 2 : 1 : 0;
    return count + count(n / 10, digit);
}

The shortest solution would be something like

public int count(int n, int d) {
    return n == 0 ? 0 : n % 10 == d ? n / 10 % 10 == d ? 2 : 1 : 0 + count(n / 10, d);
}

which is pretty unreadable unless you split it up into parts with clear names. (BTW, no guarantee that last solution is correct...)

\$\endgroup\$
2
\$\begingroup\$

You can quit the recursion when n < 8, which makes it a bit faster. The check for two consecutive eights is easily done by checking whether n % 100 = 88.

public int count8(int n) {
  if (n < 8) return 0;
  int count = (n % 10 != 8 ? 0 : n % 100 != 88 ? 1 : 2);
  return count + count8 (n / 10);
}

In the posted code, I wouldn't divide n by 10 and call count8 (n) but call count8 (n / 10) - in general you should avoid changing your own parameters, and calling count8 (n / 10) means you can move that line of code around if you want to change your code, for example to the start of the function.

\$\endgroup\$
1
\$\begingroup\$

Trying to use only one '%' and one '/' operation per call of count (why? It's a likely kind of stupid constraint posed by insecure interviewers)

public int count(int num, int dig) {
  return(count(num, dig, true, false));
}

public int count(int num, int dig, boolean wasFirst, boolean triggered) {
  if (num == 0) {
    if ((wasFirst) &&
        (dig == 0)) {
      return(1);
    }
    return(0);
  }
  boolean nextTrigger = false;
  int score = 0;
  if ((num % 10) == dig) {
    score++;
    if (triggered) {
      score++;
    }
    nextTrigger = true;
  }
  return(score + count(num / 10, dig, false, nextTrigger));
}
\$\endgroup\$
  • 2
    \$\begingroup\$ You've posted an alternate solution but haven't explained why it might be better, can you please describe how your answer is an improvement on the original code. \$\endgroup\$ – 410_Gone Jan 24 '17 at 4:25
  • \$\begingroup\$ As I explained in my post of an alternate solution, it was in anticipation of the kind of constraint sometimes imposed by interviewers. In this case, the constraint was to use only one instance each of the mod operator ('%') and div operator ('/'). You might have such a constraint in 'real life' if those were quite expensive operations. It also, along with Mr. Conrad's post below, demonstrates how to give the recursion a 'memory' of what was immediately adjacent. This may not qualify as an improvement on the original code. If that violates the spirit of this website, I am happy to delete it. \$\endgroup\$ – SplendidSplinter Jan 24 '17 at 12:58
0
\$\begingroup\$

This is quite similar to Taemyr's solution, but uses arithmetic to calculate the bonus for consecutive digits rather than an explicit test, and it avoids the glitch where the digit to match is zero by testing whether we're down to a single digit before recursing. It can also handle negative numbers.

public class Counter {
    private final int digitToMatch;

    public Counter(int match) {
        digitToMatch = match;
    }

    // map the desired digit to one, all others to zero
    private int asOne(int digit) {
        return digit == digitToMatch? 1 : 0;
    }

    public int count(int n) {
        if (n == Integer.MIN_VALUE) {
            throw new ArithmeticException("Out of range");
        }
        if (n < 0) return count(-n, -1);
        return count(n, -1);
    }

    private int count(int n, int previous) {
        int current = n % 10;
        return asOne(current) + // base value
            asOne(current) * asOne(previous) + // bonus
            (n <= 9? 0 : count(n / 10, current)); // recurse (as needed)
    }
}

If the current digit is not the sought-after digit, asOne(current) will be zero, and if the previous digit is not the sought-after digit, asOne(previous) will be zero, so the bonus asOne(current) * asOne(previous) will be zero if there are not two consecutive digits; otherwise, it will be one.

\$\endgroup\$
  • \$\begingroup\$ Could you explain in more detail how this code communicates with each other. For example, I follow more or less up to asOne as we are setting 1 to be our flag. However, when we start passing negatives I get somewhat confused. So if -1, we go to asOne and since it is not the digit to match we return a 0. Which I assume is done to ensure + 1 or + 0. Now, what is 9 in <= 9? \$\endgroup\$ – SomeStudent Jan 24 '17 at 18:37
  • \$\begingroup\$ @SomeStudent -1 is just a value that cannot match any digit. 9 is the largest possible single digit. That is testing if we are down to the last digit, in which case, don't recurse, just add in a zero. \$\endgroup\$ – David Conrad Jan 24 '17 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.