Looking for alternative algorithms
Below are the ones l have made but are being flagged as incorrect by the Online Judge on a coding website.
After declaring variable of int data type k, l received an input from the console using cin(). Since the constraints of the question read that the possible number(s) is/are between 1 and 20000, l first off opened a for loop using these conditions. At every iteration of i (one after the other), the number is tested whether its digits sum up to 10 and if they do, whether its the kth number whose digits are of sum 10.
To find the sum of digits, l used either a recursive function or an iterative method using a while loop. Hence the two snippets of codes. In both methods, the sum is calculated by finding the digits first using modular % operator and division operator /. The sum is figured out and then further tested if its equal to 10 and if Yes, it is also tested if its the K th element by means of keeping count of all previous similar elements. After all conditions are satisfied, only then is the value i outputted using cout().
#include <bits/stdc++.h>
using namespace std;
//recursion to get sum of digits.
*int sum(int d)
{
return d==0?0:d%10+sum(d/10);
}*
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int t;
cin>>t;
while(t-- >0)
{
int k;
cin>>k;
for(int i=0;i<20000;i++)
{
int total=sum(i);
if(total==10)
{
--k;
if(k==0)
cout<<i<<"\n";
}
}
}
return 0;
}
Second one, l used iterations(while loop) to deduce sum of digits
#include <bits/stdc++.h>
using namespace std;
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int t;
cin>>t;
while(t-- >0)
{
int k;
cin>>k;
for(int i=0;i<20000;i++)
{
int sum=0,d=i;
*while(d!=0)
{
sum+=d%10;
d/=10;
}*
if(sum==10)
{
--k;
if(k==0)
cout<<i<<"\n";
}
}
}
return 0;
}
So l need alternative algorithms of better efficiency. Thanks in advance
The main issue of your code is that you limit the search for values less than 20000.
In order to improve the efficiency, I added two tricks
On my PC, it takes 0.15s to calculate the maximum value (for k = 20000).
Additional explanations
In the code, the i variable corresponds to the candidates, i.e. the values that we test whether the sum of digits is equal to 10 or not.
num corresponds the the index of found solutions. A solution corresponds to a number, the sum of digits of which is equal to 10. mem[num] = i means that i is the num^th solution. k has the same meaning as in OP's code: we want to find the k^th number such that sum of digits = 10.
The two lines int kmax = 1; mem[1] = 19; use the fact that 19 is the first valid solution. This is needed to initialise the management of the mem vector, which memorizes all found solutions.
The tricks used to accelerate the process are the following:
i is equal to 10, then we know that there is no other solution between i and i+8. For example, after 27, the next solution is equal to 36. So we can do i += 9 instead of simply i++.i = 85, we can go directly to 90, i.e. nulling the least digit. This is performed with i += (10 - i%10);i += (10 - total);In practice, it could be possible to go further. For example, if i = 99000, then we could directly add 1000 instead of 10. I did not go so far, as the obtained code seems over-skill already a little bit (0.15s instead of 1s).
#include <iostream>
#include <vector>
int sum(int d) {
int ans = 0;
while(d) {
ans += d%10;
d /= 10;
}
return ans;
}
int main() {
int t;
std::cin >> t;
std::vector<int> mem(20001, 0);
int kmax = 1;
mem[1] = 19;
while(t-- >0) {
int i, k;
std::cin >> k;
int num = 1;
if (k > kmax) {
i = mem[kmax];
num = kmax;
while(true) {
int total = sum(i);
if(total == 10) {
mem[num] = i;
if (num == k) break;
num++;
i += 9;
} else {
if (total > 10) {
i += (10 - i%10);
} else {
i += (10 - total);
}
}
}
kmax = k;
}
std::cout << mem[k] <<"\n";
}
return 0;
}