count number of digit using recursive method

Question

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 program seems not able to count double '8's. Here's the code.

public int count8(int n) {
    boolean flag = false;
    if(n<10)
    {
      if (n==8)
      {
         if(flag == true)
             return 2;
         else 
         { 
             flag = true;
             return 1;
         }
      }
      else 
      {
        flag = false;
        return 0;
      }
    }

    else
       return count8(n%10)+count8(n/10);

}

I was wondering if the last line goes wrong but I don't know how to check it. Looking forward to your help. Thanks!

This could help. http://stackoverflow.com/questions/275944/how-do-i-count-the-number-of-occurrences-of-a-char-in-a-string — Lucky, Mar 22 '16 at 13:34
This looks like a homework question. Asking on stack kind of beats the point, don't you think. Ask classmates and try figure it out. There are many ways to solve it, but a hint to the most obvious one is: _add a boolean parameter_ — Kevin, Mar 22 '16 at 13:34

score 1 · Accepted Answer · answered Mar 22 '16 at 13:41

1

Pass the state (is the previous digit eight) to the method:

private static int count8(int n, boolean eight) {
  if (n <= 0)
    return 0;
  else if (n % 10 == 8)
    return 1 + (eight ? 1 : 0) + count8(n / 10, true);
  else
    return count8(n / 10, false);
}

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

answered Mar 22 '16 at 13:41

Dmitry Bychenko

180,369
20
160
215

Correct, but this is clearly a homework question. I think you should've let him try solve it himself. – Kevin Mar 22 '16 at 13:45
Thank you both! I know where my problem is now. BTW, this is not my homework. I am learning by myself and this is a problem from codingBat. Thanks a lot! – JenkinsY Mar 22 '16 at 15:30
this fails if n = 88, it returns 3 – Zeus Oct 09 '19 at 17:57
1

@Zeus: it seems to be correct "8 immediately to its left counts double" so we have `1 + 2 == 3`; please have at the `8818` example which returns `4` – Dmitry Bychenko Oct 09 '19 at 18:34

Mark · Answer 2 · 2016-03-22T13:52:56.697

1

Your flag variable is only local. There's only one time you read it: if (flag == true) and since you never change it's value before that it will always be false.

You make this a lot more complicated than it has to be though. No need for an additional parameter at all.

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

edited Mar 22 '16 at 13:52

answered Mar 22 '16 at 13:49

Mark

1,498
1
9
13

thank you for your answer! I understand where the problem is. – JenkinsY Mar 22 '16 at 15:22

score 0 · Answer 3 · answered Mar 22 '16 at 13:50

0

You can try smth like this:

public int count8(int n) {
    if (n < 10)
        return n == 8: 1 ? 0;

    int count = 0;
    String num = Integer.toString(n);
    int numLength = num.length();

    if (numLength % 2 != 0)
        num += "0";

    if ((num.charAt(numLength / 2) == num.charAt(numLength / 2 - 1)) && (num.charAt(numLength / 2) == "8"))
        count++;

    String left = num.substring(0, numLength / 2);
    int leftInt = Integer.parseInt(left);
    String rigth = num.substring(numLength / 2);
    int rigthInt = Integer.parseInt(rigth);

    return count + count8(leftInt) + count8(rigthInt);
}

answered Mar 22 '16 at 13:50

Gregory Prescott

574
3
10

it's an pure *arithmetic problem*, so converting to `String` (i.e. `String num = Integer.toString(n)`) looks ugly. – Dmitry Bychenko Mar 22 '16 at 13:55
It can be one of solutions, more algorithmic than arithmetic. Why not? – Gregory Prescott Mar 22 '16 at 14:00

Nguyen Nguyen · Answer 4 · 2018-12-08T03:49:28.930

0

C++

int count8(int n) {
    return n == 0 ? 0 : (n % 10 == 8) + (n % 100 == 88) + count8(n/10);
}

Java & C#

int count8(int n) {
    if (n==0) return 0;
    if(n % 100 == 88)
        return 2 + count8(n / 10);
    if(n % 10 == 8)
        return 1 + count8(n / 10);

    return count8(n / 10);
}

edited Dec 08 '18 at 03:49

answered Dec 07 '18 at 09:01

Nguyen Nguyen

1
1

count number of digit using recursive method

4 Answers4