KS2 - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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

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.
Now let’s start with m=1
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.
Source Code Link- https://www.codechef.com/viewsolution/24534733

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() {
// your code goes here
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
 InputReader in = new InputReader(System.in);
 OutputWriter out = new OutputWriter(System.out);
 int T = in.readInt();
 while(T-->0)
 {  int i;
	String str = in.readString();
	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;
}

}

class InputReader
{
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;
}

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

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

public String readString()
{
    int c = read();
    while (isSpaceChar(c))
        c = read();
    StringBuilder res = new StringBuilder();
    do
    {
        res.appendCodePoint(c);
        c = read();
    } while (!isSpaceChar(c));
    return res.toString();
}

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

public long readLong()
{
    int c = read();
    while (isSpaceChar(c))
        c = read();
    int sgn = 1;
    if (c == '-')
	{
        sgn = -1;
        c = read();
    }
    long res = 0;
    do
	{
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = read();
    } 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()
{
    return readString();
}

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
InputReader in = new InputReader(System.in);
OutputWriter out = new OutputWriter(System.out);

//read int
int i = in.readInt();
//read string
String s = in.readString();
//read int array of size N
int[] x = IOUtils.readIntArray(in,N);
//printline
out.printLine(“X”);

//flush output
out.flush();

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

class IOUtils
{
public static int[] readIntArray(InputReader in, int size)
{
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}
}