I'm working on the following problem:

The number n is given as input

Find out if it's monotonic?

A monotonic number is called - that number of numbers in which monotonically decrease or increase monotonically. For example: 110, 111, 122, 123, 455, 554. - are monotonic. 101, 121, 231 are non-monotonic.

Constraint: Arrays and strings cannot be used.

I wrote a function to check for a monotonically increasing number:

public static boolean isMonotonic(int num) {
    int n = num; // Copy of num to be modified
    int b = (n/10); // Step for a number if it is monotone
    n /= 10;
    if (num < 100) return true; // all two-digit numbers are monotonic
    while (n > 0 && n > b) {
        if ((n/10) != b){
            return false;
        }
        n /= 10;
    }
    return true;
}

But I don't know how to make a function for a monotonically decreasing number.

CodePudding user response：

An easy way to solve this without dealing with n/10's is converting num into a string

public static boolean isMonotonicDecreasing(int num) {
 
    //First, convert num into a string
    String numString = String.valueOf(num);
    
    //Iterate across numString - 1
    for (int i = 0; i < numString.length() - 1; i  ){
        
        //If the current digit (character at index i, converted to integer) 
        //is less than the next digit, return false
        if ((int)numString.charAt(i) < (int)numString.charAt(i 1)){
            return false;
        }
        
    }
    
    //Return true after reaching end of loop
    return true;
}

CodePudding user response：

Because according to your requirement the digits of a valid monotonic number can be equal (e.g. 110, 455) the decreasing order and increasing order can be easily confused while examining the digits. And we also have a case when all digits are equal, i.e. the number is neither increasing, no decreasing, but it's considered to be a valid monotonic number (e.g. 111).

I've come up with the following algorithm:

• Maintain three boolean flags representing three cases when a number can be considered monotonic, described above. To initialize these flags, we need to access both the first and the last digits of the given number. Because adjacent digits can be equal, only comparison of the first and the last digits would provide sufficient information regarding expected ordering of the number. Here is how all three flags would be initialized:

  • isEqual = first == last;
  • isIncreasing = first >= last;
  • isDeceasing = first <= last;

• Maintain a variable holding the value of the previous digit.

• Iterate over the digits of the given number and compare the next and previous digits. If conditions are consistent with the flags - proceed iterating further, otherwise invalidate the number returning false.

As a small optimization we can cut out all numbers that are less the then 100 because according to the requirements are monotonic.

That's how implementation might look like:

public static boolean isMonotonic(int num) {
    
    // NOTE: use Math.abs() to adjust the input if negative values are allowed
    
    if (num <= 100) return true; // early kill for small number
    
    int last = num % 10;
    int first = num / (int) Math.pow(10, (int) Math.log10(num));
    
    int prev = last;
    num /= 10;
    
    boolean isEqual = isEqual(first, last);
    boolean isIncreasing = isIncreasing(first, last);
    boolean isDeceasing = isDecreasing(first, last);
    
    while (num > 0) {
        int next = num % 10;
        
        if (isEqual && !isEqual(next, prev)) return false; // next is passed before previous because we are iterating from right to left
        
        if (isIncreasing != isIncreasing(next, prev) && isDeceasing != isDecreasing(next, prev)) {
            return false;
        }
        
        prev = next;
        num /= 10;
    }
    
    return true; // the number is proved to be monotonic
}

public static boolean isEqual(int left, int right) {
    return left == right;
}

public static boolean isIncreasing(int left, int right) {
    return left <= right;
}

public static boolean isDecreasing(int left, int right) {
    return left >= right;
}

main()

public static void main(String[] args) {
    System.out.println("Digits are equal:");
    System.out.println(111   " "   isMonotonic(111));
    System.out.println(333   " "   isMonotonic(333));
    System.out.println(999   " "   isMonotonic(999));
    System.out.println("Increasing:");
    System.out.println(189   " "   isMonotonic(189));
    System.out.println(577   " "   isMonotonic(577));
    System.out.println(779   " "   isMonotonic(779));
    System.out.println("Decreasing");
    System.out.println(775   " "   isMonotonic(775));
    System.out.println(831   " "   isMonotonic(831));
    System.out.println(99333   " "   isMonotonic(99333));
    System.out.println("Non-monotonic");
    System.out.println(101   " "   isMonotonic(101));
    System.out.println(45551   " "   isMonotonic(45551));
    System.out.println(95559   " "   isMonotonic(95559));
}

Output:

Digits are equal:
111 true
333 true
999 true
Increasing:
189 true
577 true
779 true
Decreasing
775 true
831 true
99333 true
Non-monotonic
101 false
45551 false
95559 false

CodePudding user response：

To compare if the digits are going up or down, compare the the previous digit and the current digit. Each iteration, we must update previous digit to current digit and move current digit to the next digit and shift the digits in the integer to the right.

You need two boolean variables: tracking monotonic increasing and monotonic decreasing. Finally, return the OR of the two boolean variables.

   static boolean isMonotonic(int n){
      boolean inc = true;  //assume monotonic increasing 
      boolean dec = true;  //assume monotonic decreasing
      int prev = n;     //previous is right most digit
      n/=10;               //shift digits to the right
      while(n > 0){
         int cur = n;      //current is right most digit
         inc &= prev >= cur;  //is monotonic increasing ?
         dec &= prev <= cur;  //is monotonic decreasing ? 
         prev = cur;          //previous is set to current digit
         n/=10;               //shift digits to the right.
      }
      return inc || dec;  
   }

CodePudding user response：

Let's introduce int order which is 1 if we have increasing sequence, -1 in case of decreasing sequence and 0 if we don't know it so far (for instance ...111111). Then all we should do is to llop over digits:

    public static bool isMonotonic(int num) {
      if (num > -100 && num < 100)
        return true;

      int order = 0;
      int prior = num % 10;
      
      for (; num != 0; num /= 10) {
        int current = num % 10;

        if (order > 0 && current < prior || order < 0 && current > prior)
          return false;

        if (current != prior)
          order = Math.sign(current - prior);

        prior = current;
      }

      return true;
    }

Another possibility is to try to find counter example: a digit which is bigger than its neighbors or smaller than its neighbors.