# Tidy Numbers (Code Jam ’17 Qualification Round)

Given a long number and you have to determine a number which is smaller than the number (or equal) as well as its digits must be arranged in **non-decreasing **order. Read full problem statement HERE.

Lets take some example:

**Example 1:**

132

output = 129

**Example 2:**

11110

output = 9999

**Naive approach\( (n\log_{10} n) \):**

Choose the number check its digits are arranged in the given order or not, if it is not, decrements the number and repeat above step until a sorted sequence is obtained.

This approach works fine for number \(\le 10^7\) but think of number \(\sim 10^{18}\) It would be not possible to check all combination.

Lets checkout a better approach.

**Naive approach\( (\log_{10} n)^2 \):**

We will start moving from first digit of number and find the digit after which order ( ascending ) breaks. We will reduce the digit with 1 and change all digits present to its right to ‘9’.

Now wait this is not true for every sequence lets check out 2nd example for better understanding.

Number : 11110

on applying this approach we will get sequence :- 11109 but this is still not sorted.

So this problem can be overcome by repeating above step until a sorted sequence is obtained. I.e,

11109 -> 11099 -> 10999 -> 0999 ~ 999 which is required number.

#include<bits/stdc++.h> using namespace std; int main() { int t; // Test cases cin>>t; for(int i=1;i<=t;i++) { cout<<"Case #"<<i<<": "; string s; // inputting number in a string cin>>s; bool sorted = false; while(!sorted) { sorted = true; for(int i=0;i<s.size()-1;i++) { if(s[i] > s[i+1]) { s[i]-=1; for(int j=i+1;j<s.size();j++) s[j]='9'; sorted = false; break; } } } if(s[0]!='0') // if a leading '0' is not in sequence cout<<s; else for(int i=1;i<s.size();i++) // remove leading '0' cout<<s[i]; cout<<endl; } return 0; }

This article is contributed by Ravi Kant. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.