Home > Mobile >  Find the N-monotonic number
Find the N-monotonic number

Time:10-11

I'm working on the assignment, which requires to find the N-th monotonic number (a number which digits form increasing or decreasing sequence).

Find the N-th monotonic number starting from zero 0 (i.e. index N start from zero and zero is the first monotonic number).

A number considered to be monotonic if it has all the digits either in increasing or decreasing order.

Note: all numbers which consist of only one or two digits are considered to be monotonic.

Example:

Monotonic numbers: 1234, 4321, 13579

Non-monotonic numbers: 1432, 89461

You're not allowed to use an Array or a String.

I understand how to iterate over the digits of a number, but I'm not getting how to combine this with a check if the number is monotonic.

This is the code I have so far:

static int functionForCountNumbers(){
    int n = ReadNumber();
    int min;
    int count = 0;
    while (n > 0){
        min = n % 10;
        n /= 10;
        count  = 1;

    }
    return count;
}

CodePudding user response:

Remember if the first pair of digits is in increasing or in decreasing order.

Remember the last digit.

For every new digit check if it form the same order with the last digit.

Assign current digit to last digit

CodePudding user response:

This problem can be split into two parts, which you can address separately:

  • Generating candidate numbers.

  • Checking if the number is a monotonic number.

To accomplish the first part, declare the counter variable representing the index of a monotonic number as you did, and the variable holding a value of a candidate number.

Then in the loop you need to check each candidate number, and if it's a monotonic number, increment the count.

Since according to problem description, all numbers containing one or two digits are considered to be monotonic we can treat all n<100 separately, and start checking numbers starting from 123 which is the fist monotonic three-digit number.

Note: for simplicity, I will stick with the definition of a monotonic number as either strictly increasing or decreasing. I advise you consult with your professor, because the requirement of considering all two-digit numbers, including the numbers containing repeated digits like 33 and 99 might imply that a monotonic number can contain equal digits. So, even if my definition is not precise, it would give you the understanding of the algorithm.

That's how the first part might be implemented:

public static int functionForCountNumbers() {
    int n = readNumber();
    
    if (n < 0) throw new IllegalArgumentException("number shouldn't be negative");
    
    // or allow the user to retry
    // while (n < 0) {
    //     System.out.println("number shouldn't be negative");
    //     n = readNumber();
    // }
    
    if (n < 100) return n;
    
    int count = 99;
    int candidate = 123; // the first monotonic number, which should correspond to n = 100
    
    while (count < n) {
        if (isMonotonic(candidate)) count  ;
        candidate  ;
    }
    
    return candidate;
}

To find out whether a candidate number is a monotonic or not you can compare the first subsequent pair of digits and store the result into a variable. Then continue comparing the rest digits in the loop, tracking the previous digit and result of the previous comparison.

If no inconsistencies were encountered while comparing adjacent digits, the number has been proved to be monotonic.

That's how this logic can look like:

public static boolean isMonotonic(int num) {
    if (num < 100) return true;
    
    int prev = num % 10;
    num /= 10;
    boolean isIncreasing = isIncreasing(num % 10, prev);
    
    while (num > 0) {
        if (isIncreasing != isIncreasing(num % 10, prev)) {
            return false;
        }
        prev = num % 10;
        num /= 10;
    }
    return true;
}

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