Найти N-е наименьшее круглое целое число

Question

Целое число является круглым, если оно больше 0, а сумма его цифр в десятичном представлении кратна 10. Найдите N-е самое маленькое круглое целое число.

1≤N≤10 ^ 18

Я пробовал наивный подход, но решение не подходит для больших ограничений.

#include <bits/stdc++.h> 
 using namespace std; 

 int sumOfDigits(int n) 
 { 
  int sum = 0; 
  while (n > 0) { 
    sum += n % 10; 
    n /= 10; 
   } 

    return sum; 
 } 

 int findNum(int n) 
 { 
   int c=0, num=0;

    while (c != n) { 
    num++; 
    int sum = sumOfDigits(num); 
    if (sum % 10 == 0) 
        c++; 
 } 

  return num; 
 } 

 int main() 
{ 
 int t, n;
 cin>>t;
 while(t--){
    cin>>n;
    cout<<findNum(n)<<endl;
 }
 } 

Есть ли хороший подход для решения этой проблемы. Пожалуйста, не вставляйте полностью решение, я просто хочу, чтобы подход решил это.

Я также попробовал другой подход ... но решение не работает нормально.

  public static long findNth(int n) 
  { 
    long nthElement = 19 + (n - 1) * 9; 
    int outliersCount = (int)Math.log10(nthElement) - 1; 

    nthElement += 9 * outliersCount; 
    return nthElement; 
  } 

Там будет серия: 19, 28, 37, 46, 55, 64 ..... но не забудьте удалить 100, 1000 ... и т. Д.

Учитывая это, я пробовал решение выше, но оно не работает.

Я использую один из предложенных подходов. Но это тоже не работает нормально.

int sumOfDigits(int n) 
{ 
int sum = 0; 
while (n > 0) { 
    sum += n % 10; 
    n /= 10; 
} 
if(sum%10==0) return 0;
else if(sum<10) return 10-sum;
return 10-sum%10;
} 

long long findNum(int n) 
{ 
return n*10+sumOfDigits(n);
} 

Answer 1

Один важный совет: если первые n-1 цифры целого числа n являются фиксированными, существует ровно одна цифра, которую можно использовать в качестве последней цифры для выполнения условия.Другими словами, есть ровно одно целое число, которое удовлетворяет требуемому условию в каждых 10 целых числах (начиная с 10).Исходя из этого, существует очень простое решение проблемы, которое генерирует ответ напрямую, а не перечисляет целые числа по одному и проверяет условие.

Answer 2

Если вы посмотрите на числа, удовлетворяющие этому критерию

19, 28 ... 91, 109, 118 ... 190, 208, 217 ... 280, 299, 307 ... 370, 389, 398, 406 ... 460, 479 ... 497 , 505 ... 550, 569 ... 596, 604 ... 640, 659 ... 695, 703 ... 730, 749 ... 794, 802 ... 820, 839 ... 893, 901 , 910, 929 ... 992, 1009 ...

вы видите, что расстояние между соседними круглыми числами чаще всего равно 9 (всякий раз, когда я печатал '...' выше). Однако имеются большие (например, между 280 и 299) и меньшие промежутки (например, между 794 и 802). При внимательном рассмотрении выясняется, что число N(k) круглых чисел меньше k удовлетворяет:

N(100)   = 9;
N(1000)  = 99;
N(10000) = 999; etc.

Вы можете проверить это и найти шаблон для произвольных больших чисел. Затем вы можете использовать этот результат, чтобы найти обратный результат, то есть k(N), который является вашим ответом, не более чем на log(N) шагах.

Answer 3

Попробуйте найти какой-либо шаблон в числах, удовлетворяющих этому условию, и вы сможете найти более эффективное решение, чем просто итерация по каждому числу.