Analysis: Odometer by Nathan Pinsker

Although the numbers we are working with can be quite large (up to 10^16!) it actually turns out that the number of interesting numbers is quite small. In fact, we can construct all such numbers by taking every number with repeated digits (e.g. 3333333333) and changing exactly one digit, then checking whether the new number is between X and Y. There are at most 17 digits in our number that we can change, and there are 9 possible new digits to change it to, so the number of interesting numbers we could possibly find is about 17*9, which is definitely small enough to deal with. We can solve this problem by actually constructing all possible numbers composed of a single unique digit, then brute-force changing these numbers in every possible allowed way, and checking each of these numbers to see if it is in the interval [X, Y].

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cassert>

using namespace std;

int main() {
  freopen("odometer.in", "r", stdin);
  freopen("odometer.out", "w", stdout);

  long long X, Y;
  cin >> X >> Y;

  int result = 0;
  for(int sz = 3; sz <= 17; sz++) {
    for(int d0 = 0; d0 < 10; d0++) {
      string S(sz, '0' + d0);
      for(int d1 = 0; d1 < 10; d1++) {
        if(d0 == d1) continue;

        for(int i = 0; i < sz; i++) {
          S[i] = '0' + d1;

          long long num = atoll(S.c_str());
          if(S[0] != '0' && X <= num && num <= Y) {
            ++result;
          }

          S[i] = '0' + d0;
        }
      }
    }
  }
  cout << result << endl;
  return 0;
}