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

@kid_delta0001 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- CodeChef: Practical coding for everyone

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