PROBLEM LINK:
Setter: Kartik Singhal
Tester: Radoslav Dimitrov
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
Cakewalk
PREREQUISITES:
Observation, Pattern
PROBLEM:
Find the nth positive integer whose digit sum is divisible by 10.
EXPLANATION
Fact: In every 10 consecutive positive numbers, exactly only one of them will be divisible by 10.
Claim: For every positive integer i, there exist only one number between [10*i,10*i+9] whose digit sum is divisible by 10.
Proof: Let us denote D(i) as digit sum of i. Now D(i*10+k) = D(i*10) + k \forall k( 0 \leq k \leq 9) (because k will replace 0 in oneās place). And now D(i*10),D(i*10+1),....D(i*10+9) will be be equal to D(i*10),D(i*10)+1,...,D(i*10)+k. These are 10 consecutive positive integers, Hence exactly one of them is divisible by 10.
Now, we can see by checking with hand that none of [1,9] are divisible by 10.
Claim: nth positive integer whose digit sum is divisible by 10 will be in range [10*n,10*n+9].
Proof: Proof by induction
Base case: 1st positive number is 19 which belongs to [10,19].
Let kth positive integer \in [k*10,k*10+9].
Now, from above claim (k+1)th cannot be in range [k*10,k*10+9]. Hence it must be in [(k+1)*10,(k+1)*10+9] again by same claim.
So now, we can check those 10 numbers and output the answer as which ever satisfies.
TIME COMPLEXITY
O(log(n)) because there are log(n) digits in .
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define pb push_back
#define fs first
#define sc second
#define PP pair<ll,ll>
int main ( )
{
ios_base::sync_with_stdio(false);
cin.tie( NULL ) ;
/*
ifstream inFile;
inFile.open("input5.txt");
if (!inFile) {
cerr << "Unable to open file datafile.txt";
exit(1); // call system to stop
}
ofstream my;
my.open("output5.txt");
*/
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
int sum=0;
for(int i=0;i<s.length();i++)
{
sum+=s[i]-'0';
}
s=s+char('0'+(10-sum%10)%10);
cout<< s<<"\n";
//my << s<<"\n";
}
//inFile.close();
}
Tester's Solution
import sys
def read_line():
return sys.stdin.readline()[:-1]
def read_int():
return int(sys.stdin.readline())
def read_int_line():
return [int(v) for v in sys.stdin.readline().split()]
############
# Solution #
T = read_int()
for _test in range(T):
N = read_line()
d = 0
for i in N:
d = (d + int(i)) % 10
d = (10 - d) % 10
N += str(d)
print(N)
Editorialist's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
int gg[123][123];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
gg[0][0]=1;
int iinf=inf;
iinf*=inf;
//cout<<iinf<<endl;
int i,j,k;
f(i,1,30){
rep(j,10){
rep(k,10){
gg[i][(j+k)%10]+=gg[i-1][k];
if(gg[i][(j+k)%10]>iinf)
gg[i][(j+k)%10]=iinf;
}
}
}
while(t--){
int n;
cin>>n;
n++;
int sofar=0,lef,cur,previ;
string ans="";
//cout<<gg[29][0]<<endl;
fd(i,29,1){
cur=0;
previ=0;
rep(j,10){
lef=10-sofar-j;
lef%=10;
lef+=10;
lef%=10;
cur=previ+gg[i-1][lef];
if(cur>=n){
//cout<<cur<<" "<<i<<" "<<j<<" "<<lef<<" "<<n<<endl;
//cout<<j<<endl;
n-=previ;
ans+=(char)('0'+j);
//cout<<ans<<end;l;
sofar+=j;
break;
}
previ=cur;
}
}
rep(i,ans.length()){
if(ans[i]!='0')
break;
}
f(j,i,ans.length()){
cout<<ans[j];
}
cout<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 