Hello, I'm a beginner in competitive programming.

I really enjoyed the 1520B problem called Ordinary Numbers : https://codeforces.com/problemset/problem/1520/B

I observed that @MikeMirzayanov's tutorial uses a brute-force method to solve this : https://codeforces.com/blog/entry/90342

However, it is possible, to solve the problem without using bruteforce, at all.

Here's my solution which has been accepted by the virtual judge : https://codeforces.com/contest/1520/submission/119706686

I hope it's useful to you all. After all, we'll all learn together.

Thank you :)

// URL  : https://codeforces.com/problemset/problem/1520/B
// NOTE : Really good problem. Loved the logic behind it. AMAZING PROBLEM!!!
//

#include <iostream>
#include <algorithm>
#include <cmath>

#pragma GCC optimize("O3")

#define sl long long
#define nl "\n";

using namespace std;

sl memo[100];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	sl t;
	cin >> t;

	// create a memoization table using which we can create unique numbers
	// just from the first digits of some number we're currently analyzing
	//
	memo[0]  = 0;
	memo[1]  = 1;
	memo[2]  = 11;
	memo[3]  = 111;
	memo[4]  = 1111;
	memo[5]  = 11111;
	memo[6]  = 111111;
	memo[7]  = 1111111;
	memo[8]  = 11111111;
	memo[9]  = 111111111;
	memo[10] = 1111111111;
	memo[11] = 11111111111;
	memo[12] = 111111111111;
	memo[13] = 1111111111111;

	// for [0] = 0 unique numbers as range is 1<=n<=10^9
	// for [1:10] = 9 unique numbers for 1 digit numbers
	// for [10:100] = 9 unique numbers for 2 digit numbers
	// for [100:1000] = 9 unique numbers for 3 digit numbers
	// for [1000:10,000] = 9 unique numbers for 4 digit numbers
	//
	while(t--)
	{
		sl n;
		cin >> n;

		// number of digits in the number
		sl ndigits = floor(log10(n)+1);

		// maximum possible unique numbers for a digit of length ndigits
		sl maxunos = ndigits * 9;

		// get the first digit of n
		sl fdigit = n/pow(10, ndigits-1);

		// get the unique number that starts with fdgit and ends with fdigit
		// and contains ndigits digits : 12345 -> 11111 ; 41234 -> 4444
		//
		sl m =  memo[ndigits]*fdigit;

		// incase the given n is not a unique number, we need to analyze
		// what's the correct number of unique numbers present in the given
		// range. we need to do this, since maxunos needs to be corrected.
		//
		sl neg = 0;

		if(n<m)
		{
			neg = 9-fdigit+1;
		}
		else
		if(n>=m)
		{
			neg = 9-fdigit;
		}

		// correct answer
		sl ans = maxunos - neg;

		cout << ans << nl;
	}

	cout << flush;
	return 0;
}