Java : write recursive function and check if one digit is even and the other not-CodePudding

I am struggling with an exercise I got. I need to write a recursive function that checks if one digit is odd and the other one is even, it is need to toggle in any digit.

For example,

123 is true (3 is odd, 2 is even, 1 is odd)
1234 is also true
12354 is false (4 is even, 5 is odd and 3 is odd)

The digits must be alternating between even and odd.

If the number is only 1 digit you return true. All numbers are positive.

Below is the function I wrote, and I can't find where my mistake is :/

//Assumption : num > 0
//this function will return if true or not if number is alternating
public static boolean isAlternatingNumber(int num) {
    boolean flag;
    if(num < 10) {
        return true;
    }
    else {
        flag =  isAlternatingNumber(num/10);
        int n = num% 10;
        if(num % 2 == 0 && flag) {
            return true;
        }else {
            return false;
        }
    }
}

CodePudding user response：

Assuming the original function signature public static boolean isAlternatingNumber(int num) cannot be changed, you can solve this problem by using a recursive helper function to add additional parameters to your recursive function.

Here is an example of how you might solve this problem by using a recursive helper function;

class Main {  
  public static void main(String args[]) { 
    System.out.println("123: "   isAlternatingNumber(123)); // true
    System.out.println("1234: "   isAlternatingNumber(1234)); // true
    System.out.println("12354: "   isAlternatingNumber(12354)); // false
  }
  
  // Original function with unmodified signature
  public static boolean isAlternatingNumber(int num) {
    // Base case, returns true if num is only 1 digit
    if (num < 10) {
        return true;
    }
    
    /*
          First argument; num with its first digit "sliced" (if num is 123, num / 10 is 12)
          Second argument; Whether or not if the first digit of num is even (if num is 123,
        (num % 10) % 2 == 0 is false, as (num % 10) gives 3, and 3 % 2 is 1, as 3 is an odd number)
    */
    return findIfAlternating((num / 10), (num % 10) % 2 == 0);
  }

  /**
  * Recursive helper function to find if a given number is alternating
  * between odd and even (or vice versa) digits
  * @param num number to be checked, without its first digit
  * @param isCurrentDigitEven whether or not if the first digit of the number to be checked is even
  */
  public static boolean findIfAlternating(int num, boolean isCurrentDigitEven) {
    boolean isNextDigitEven = (num % 10) % 2 == 0;
    
    // Base case, returns true if the digits are alternating between odd and even
    if (num < 10) {
        return (isCurrentDigitEven ^ isNextDigitEven); // ^ is the XOR operator in Java, returns true if either one of the variables are true, and returns false if both variables are false or true
    }  
    
    return (isCurrentDigitEven ^ isNextDigitEven) && findIfAlternating((num / 10), isNextDigitEven);
  }
}

CodePudding user response：

For the last two digits of the number to be alternating even/odd, either the number is even and the number divided by ten is odd or vice versa (unless the number is less than ten which is considered as "true"), i.e.

(num % 2 == 0 && (num / 10) % 2 == 1) || (num % 2 == 1 && (num / 10) % 2 == 0) || num < 10

If the above expression returns true (and num is greater than ten), then repeat for num / 10.

public static boolean isAlternatingNumber(int num) {
    if (num < 10) {
        return true;
    }
    else {
        int rem1 = num % 2;
        int rem2 = (num / 10) % 2;
        boolean flag = ((rem1 == 0 && rem2 == 1) || (rem1 == 1 && rem2 == 0));
        return flag && isAlternatingNumber(num / 10);
    }
}

flag is true if rem1 and rem2 do not have the same value.

return flag && isAlternatingNumber(num / 10);

If flag is false, Java will not [recursively] call method isAlternatingNumber.

CodePudding user response：

This question can actually be considered (and so tagged?) as algorithmic. That would gravitate much more attention, interesting implementations, reactions, advices, etc.

Since OP provided very much close-to-right solution, any 1 correction leads to working algorithm. I just post possible evaluation of the idea of OP.

public static boolean isAlter(int num, boolean isPrevEven) 
{
    int next = (num - num % 10) / 10;
    boolean isCurrEven = num % 2 == 0;
    boolean isOk = (isCurrEven && !isPrevEven) || (!isCurrEven && isPrevEven);

    if (isOk) 
         return next == 0 || isAlter(next, isCurrEven);
    else return false;
}

And what is more interesting on this question is what are the requirements to the accepted algorithm? E.g. time limit, memory usage limit, size of data, or mb any big-o complexity limits.

Recursive algorithms most often can be rewritten in iterative way, which also often leads to time / memory consumption improvement. Yet, recursion is elegant, and if it does not contradict requirements or efficiency, nothing bad at all. Just remember to make correct base cases, so recursion does not go to infinity, which causes StackOverflow error.

PS: Should method accept only 1 argument, it is surely not an issue:

public boolean isAlternatingNumber(int num) 
{
    boolean isEven = num % 2 == 0;
    return isAlter(num, !isEven);
}

CodePudding user response：

Regex to the rescue:

public static boolean isAlternatingNumber(int num) {
    return !(""   num).matches(".*([02468]{2}|[13579]{2}).*");
}