CODEWITHSUNDEEP
c++algorithmmath
Nitin Singhal
Nitin Singhal

Reputation: 55

Find the N-th smallest round integer

An integer is round if it is greater than 0 and the sum of its digits in decimal representation is a multiple of 10.Find the N-th smallest round integer.

1≤N≤10^18

I have tried the naive approach, but the solution is not working fine for large constraint.

#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;
 }
 }

Is there any good approach to solve this problem. Please don't paste the whole solution I just want the approach to solve this.

I have tried another approach also..but the solution is not working fine. 

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

    nthElement += 9 * outliersCount; 
    return nthElement; 
  }

There will series form: 19, 28, 37, 46, 55, 64.....but remember to remove 100, 1000...so on.

Considering this I have tried the solution above but it's not working.

I'm using one of the approaches answered. But this is not working fine too..

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);
}

Upvotes: 1

Views: 793

Answers (3)

GZ0
GZ0

Reputation: 4263

One important hint: If the first n-1 digits of an n-digit integer are fixed, there exists exactly one digit that can be used as the last digit to satisfy the condition. In other words, there is exactly one integer that satisfies the required condition in every 10 integers (starting from 10). Based on this there is a very simple solution to the problem that generates the answer directly rather than enumerating integers one by one and verifying the condition.

Upvotes: 3

Walter
Walter

Reputation: 45424

If you look at the numbers satisfying this criterion

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 ...

you see that the distance between adjacent round numbers is most often 9 (whenever I printed '...' above). However, there are bigger (e.g. between 280 and 299) and smaller gaps (e.g. between 794 and 802). A close inspection reveals that the number N(k) of round numbers less than k satisfies:

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

You may want to verify this and find a pattern for arbitrary large numbers. Then you can use that result to find the inverse, i.e. k(N), which is your answer, in at most log(N) steps.

Upvotes: 2

Bal&#225;zs Kovacsics
Bal&#225;zs Kovacsics

Reputation: 701

Try to find some pattern in the numbers that fulfil this condition, and you can find a more efficient solution than just iterating over every number.

Upvotes: 2

Related Questions