This is second problem in Code jam Qualification Round 2017 . Here is the original problem. Tatiana likes to keep things tidy. Her toys are sorted from smallest to largest, her pencils are sorted from shortest to longest and her computers from oldest to newest. One day, when practicing her counting skills, she noticed that some integers, when written in base 10 with no leading zeroes, have their digits sorted in non-decreasing order. Some examples of this are 8, 123, 555, and 224488. She decided to call these numbers tidy. Numbers that do not have this property, like 20, 321, 495 and 999990, are not tidy.

Tatiana just finished counting all positive integers in ascending order from 1 to N. What was the last tidy number she counted?

This problem is open for practice.You can solve it on Codejam first, before reading this solution.

At my first glance, the solution seems simple. Read the given number. Check the number if tidy or not by comparing each digits. If the number is tidy, then print that number as solution or else decrease the number by one and again check for tidy condition. Continue this process until you get the last tidy number. Yes. clearly it is one way of solving this problem. And definitely you will get the solution. But at what cost ? Consider the below sample given.

Input

4

132

1000

7

111111111111111110

Output

Case #1: 129

Case #2: 999

Case #3: 7

Case #4: 99999999999999999

For the number 132, 1000 and 7 the above solution will work very well and simple. What about the number 111111111111111110 ? I have implemented the solution by above method and executed it. Even after 5 minutes the application keeps on running. So this is not a smart solution and you need to look for some smart solution to solve this problem.

Solution

Look at the below examples starting from the minimum.

Case 1:

9 - Yes it is Tidy number.

99 - Again a Tidy Number!

98 - Not a Tidy Number. The previous possible Tidy number is 89

87 - Not a Tidy number. The previous possible Tidy number is 79

76 - Not a Tidy number. The previous possible Tidy number is 69

132 - Not a Tidy number. The previous possible Tidy number is 129

Case 2:

Similarly for higher digits.

9999999 - A Tidy Number!

988888 - NOT a Tidy Number. The previous possible Tidy number is 899999

211111 - NOT a Tidy Number. The previous possible Tidy number is 199999

2341111 - NOT a Tidy Number. The previous possible Tidy number is 2339999

100000 - NOT a Tidy Number. The previous possible Tidy number is 99999

If you observe the above examples carefully, you can get the logical behind this tidy number. The logic behind this problem is,

Step 1 : Read the given number.

Step 2 : Check whether given number is Tidy starting from the MSD (Most Significant Digit)

Step 3 : If it is Tidy number, then print the given number as solution.

Step 4 : If NOT Tidy, save the digit place where Tidy condition failed. (i.e Current Digit place < Previous place number) **Step 5 **: Subtract that digit place by one and change all other fore-coming number to ‘9’. **Step 6 **: Print the number as Solution.

Special cases:

In the above steps, you need to consider few special cases. Consider the below number.

149998

This is NOT A TIDY number, since LSD (Least Significant Digit) 8 fails to satisfy the Tidy condition. i.e (8 is NOT greater than or equal 9 ) . So if you apply the above logic blindly, you will end up with 149989 as solution. Again this is NOT A TIDY number. So what’s wrong with our logic? The thing is, we need to careful when we are getting repetitive number. The work-around is, count the number of consecutive repetitive numbers. When ever we are facing with tidy property failure, the correction has to be applied at the start of that repetitive number. In this case, the solution is, 148999.

Program in C++

Now let us move to the programming part. So far we have the logic. Now it’s time to implement it in any one of the programming languages. Here I used C++. Without thinking about the large dataset, first I implemented this logic using direct method. i.e integer numbers, modulus and division operators. The solution was also accepted as correct. The another problem came to light only when I tried to solve for large dataset. This time it was due to size of integer variables. Therefore I either need to use larger data types which hold upto 1018 range or implement it in some other way. I decided to process the numbers as strings like the classic 100 digit addition program in C. The solution for both large and small dataset is highlighted in the below code block.

For complete source code, you can get it from below github repository.

https://github.com/s-gopinath/Codejam_2017

int No_Of_Trial; 
cin >> No_Of_Trial;
for(int Trial= 1;Trial<=No_Of_Trial;Trial++)
{
  //Get the last counted number by her
  string N; 
  cin>>N;
  string tidy_number;
  
  //First check if the given number if tidy
  string temp = N;
  bool IsTidy = false;
  IsTidy = IsTidyNumber(N);

  if(IsTidy)
  {
    tidy_number = N;
  }
  else
  {
    //find the previous tidy number
  
     temp = N;
     int tidy_failure_at =  current_digit;
      
    if(bISlastNum_Repitative)
 tidy_failure_at = tidy_failure_at - repeate_count;

    tidy_failure_at = tidy_failure_at - 1;
    int temp_num1 = temp[tidy_failure_at]-'0';
      
    if(temp_num1 == 1)
    {
      //in this case we have to skip LSB since we are reducing one place
      for(int i = tidy_failure_at;i<temp.length()-1;i++)
      {
        temp[i] =  '9';
      }

      temp[temp.length()-1] = '\0';
      
    }
    else
    {
      temp[tidy_failure_at] = temp[tidy_failure_at]-1;
      for(int i = tidy_failure_at+1;i<temp.length();i++)
      {
 temp[i] = '9' ; 
      }
    }

    tidy_number = temp;// * Number_place ) - 1;
  }
    
  //Print the solution here

   printf("Case #%d: ", Trial);
   printf("%s\n", tidy_number.c_str());

}//End of No.Of.Trial for loop()