/*https://code.google.com/codejam/contest/3264486/dashboard#s=p1 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. She just finished counting all positive integers in ascending order from 1 to N. What was the last tidy number she counted? Input Small dataset Large dataset 1 ≤ N ≤ 1000 1 ≤ N ≤ 10^18. This is an analysis of two different kinds of algorithms to show the difference in complexity. */ #include #include #include #include #include using namespace std; string toString(unsigned long i); string delZero(string number); bool isTidy(string number); string decrementString(string number); //bad way string rebuildString(string number); //better way int main() { clock_t t; string start = "76543210"; string num; int func; // bad algorithm clock test: t = clock(); cout << "Start: " << start << endl; num = start; func = 0; do{ if (!isTidy(num)) { num = decrementString(num); func++; } }while (!isTidy(num)); cout << "End: " << num << endl; t = clock()-t; cout << "Function Calls: " << func << endl; cout << "Clock-ticks: " << t << endl; cout << "----------------------------" << endl; // better algorithm t = clock(); num = start; func = 0; cout << "Start: " << start << endl; do{ if (!isTidy(num)) { num = rebuildString(num); func++; } }while (!isTidy(num)); cout << "End: " << num << endl; t = clock()-t; cout << "Function Calls: " << func << endl; cout << "Clock-ticks: " << t << endl; return 0; } string toString(unsigned long i) { stringstream ss; ss << i; return ss.str(); } bool isTidy(string number) { if (number.length() <= 1) { return true; } for (int i = 0; i number[i+1]) { return false; } } return true; } string delZero(string number) { number = number.substr(1); return number; } string rebuildString(string number) { for (int i = 0; i < number.length() - 1; i++) { if (number[i] > number[i + 1]) { if (number[i] == '1') { number[i] = '0'; for (int j = i + 1; j < number.length(); j++) { number[j] = '9'; } } else { number[i]--; for (int j = i + 1; j < number.length(); j++) { number[j] = '9'; } } } } while(number[0]=='0') number=delZero(number); return number; } string decrementString(string number) { bool flag = false; int len = number.length()-1; do { if (number[len] == '0') { flag = true; number[len--] = '9'; } else { flag = false; number[len]--; len--; } } while (flag == true); while(number[0] == '0') number = delZero(number); return number; }

Complexity comparison "Tidy Numbers"