Наивное решение O(n^2)

naive_solution.cpp

#include <iostream>

/*
  Вспомогательный метод. Проверяет содержит ли 
  число num в себе цифру k. Работает за O(n)
*/
bool contains(int num, int k) {
  if (k > 9) {
    return false;
  }
  while(num != 0) {
    if ((num%10) == k) {
      return true;
    }
    num /= 10;
  }
  return false;
}

/*
    Метод решения задачи. В цикле по всей последовательности чисел
    проверям содержит ли число цифру k. Поскольку содержит в себе 
    вызов метода в цикле со сложностью O(n), то его собственная сложность
    является O(n^2)
*/
unsigned int solution(int n, int m, int k) {
  if (k > 9) {
    return 0; 
  }
  unsigned count = 0;
  for (int i=n; i<=m; i++) {
    if (contains(i, k)) {
      count++; 
    }
  }
  return count;
}

int main() {
  // test data от 0 до 100
  std::cout << solution(0,100,9) << std::endl;
  return 0;
}