# KS2 - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Setter: Kartik Singhal

Editorialist: Teja Vardhan Reddy

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

return [int(v) for v in sys.stdin.readline().split()]

############
# Solution #

for _test in range(T):

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

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

8 Likes

Here is my approach:

Step 1:
Brute Force all such nth numbers till n = 10000

Step 2:
Observe the very simple pattern with these numbers.
Pattern -
Letās suppose that we are looking for the 6358th such number.
The answer would be just 6358 X 10 + (Last Digit). The last digit should be choosen suitably such that the sum of digits is divisible by 10. In our case, the answer is 63588 as 6+3+5+8+8 = 30.

Step 3:
You are done

My Code
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long int
#define rep(i,n) for(int i(0);i<n;i++)
#define fast  ios_base::sync_with_stdio(0); cin.tie(0);
#define mod 1000000007

ull dig(ull n){
ull ans=0;
while(n>0){
ans+=n%10;
n/=10;
}
return ans;
}

int32_t main() {
fast;

ull t;
cin>>t;

while(t--){
ull n,app,near;
cin>>n;

if(dig(n)%10 == 0){
near = dig(n);
}
else{
near = dig(n) - dig(n)%10 + 10;
}
app = near - dig(n) + 10*n;
cout<<app<<"\n";

}
return 0;
}

14 Likes

There is a formula on OEIS: https://oeis.org/A094677

5 Likes

Can anyone tell me why my solution is wrong? Itās using the same logic.
https://www.codechef.com/viewsolution/24787769

@satyankar_2005 isnāt that the same algorithm? By checking the range [kā10,kā10+9], we are indirectly looking for the last digit whose addition will make the digit sum be divisible by 10.

1 Like

My approach was given partial points, but I cannot find what is wrong in it.
Let p be a round number then for some n,
p={x_n}10^n + ... + x_0 such that x_n + x_{n-1} + .. + x_0 =10m for some m.
Now substitute x_0 from the second equation into first and we get,
p={x_n}(10^n-1) + ...+x_i(10^i-1)+...+10m
Now p is a round number \forall m \ge 0 and \forall i\ge 1 such that 0\le x_i \le9.
Therefore a tuple (x_1,x_2,..,x_n,m) defines a round number uniquely.
And letās say we have to find Nth round number. Let N be a k digit number.
Now my claim is that x_1,..,x_k are the k digits of N where x_i is the ith digit .
Now if for some N the corresponding p does not have the sum of digits a multiple of 10, increment the value of m by 1 till you donāt get a number whose digits sum up to multiple of 10.
This algorithm showed WA for task 3,4,5.

You should use unsigned long long, because when u will multiply n by 10 it will be at worst 10^19 which wonāt fit in long.

1 Like

Thereās no unsigned long long in Java and long can hold upto 2^64 which is greater than 10^19.

Idk java, but I came to heard about BigInteger class, what about it?

did exactly the same wayā¦

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

int main() {
int t; cin>>t; while(tā){
long long int n,temp,sum=0,rem,actual;
cin>>n;
temp=n;
while(temp!=0)
{
rem=temp%10;
sum+=rem;
temp=temp/10;
}
if(sum%10==0)
actual=n10;
else
actual=n
10+(10-(sum%10));
cout<<actual<<endl;}
return 0;
}

Can anyone tell whatās wrong with this code ā¦

I too observed the same patternā¦ felt like a douchebag until nowā¦

I can use that but thatās super unnecessary here because like I said, long can go upto 2^64 and should be enough. BigInteger can hold even bigger numbers and that is rarely required.

cant believe myself as i did not observe those patterns.thanks for the editorials

error is there ull doesnot a name type and int32_t doesnot a name type
pls explain the code in simple c++ lan

ull is a macro of unsigned long long int and int32_t means a 32-bit integer.
If the code doesnāt run , check if you copied the macros properly (define)

how to approach this ques. if instead of 10 any other number is given?

Hereās my code
why does it give WA for int(k/10) when (k//10) passes all the test cases?(line 9)

my Solution is Quite SIMPLE AND BASED ON THE SAME FACT
import java.util.;
import java.io.
;
import java.lang.*;
class cd184
{

public static void main(String args[])throws IOException
{
try{
//takign input through IO
OutputWriter out = new OutputWriter(System.out);
while(T-->0)
{  int i;
int sum = DIGITS(str);
if(sum%10==0)
{
out.printLine(str+"0");
}else
{
sum = 10-sum%10;
out.printLine(str+Integer.toString(sum));
}

out.flush();
}

out.close();
}
catch(Exception e){
e.printStackTrace();
}


}

static int DIGITS(String str)
{
int SUM = 0;
for(int i=0;i<str.length();i++)
{
SUM+=Character.getNumericValue(str.charAt(i));
}
return SUM;
}

}

{
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream)
{
this.stream = stream;
}

{
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars)
{
curChar = 0;
try
{
}
catch (IOException e)
{
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

{
while (isSpaceChar(c))
int sgn = 1;
if (c == '-')
{
sgn = -1;
}
int res = 0;
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

{
while (isSpaceChar(c))
StringBuilder res = new StringBuilder();
do
{
res.appendCodePoint(c);
} while (!isSpaceChar(c));
return res.toString();
}

while (isSpaceChar(c))
int sgn = 1;
if (c == '-')
{
sgn = -1;
}
double res = 0;
while (!isSpaceChar(c) && c != '.')
{
if (c == 'e' || c == 'E')
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
}
if (c == '.')
{
double m = 1;
while (!isSpaceChar(c))
{
if (c == 'e' || c == 'E')
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
}
}
return res * sgn;
}

{
while (isSpaceChar(c))
int sgn = 1;
if (c == '-')
{
sgn = -1;
}
long res = 0;
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public boolean isSpaceChar(int c)
{
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public String next()
{
}

public interface SpaceCharFilter
{
public boolean isSpaceChar(int ch);
}


}

class OutputWriter
{
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream)
{
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer)
{
this.writer = new PrintWriter(writer);
}

public void print(Object... objects)
{
for (int i = 0; i < objects.length; i++)
{
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}

public void printLine(Object... objects)
{
print(objects);
writer.println();
}

public void close()
{
writer.close();
}

public void flush()
{
writer.flush();
}


}

/*

USAGE

//initialize
OutputWriter out = new OutputWriter(System.out);

//read int array of size N
//printline
out.printLine(āXā);

//flush output
out.flush();

//remember to close the
//outputstream, at the end
out.close();
*/

class IOUtils
{