In this HackerEarth A beauty factor problem solution you are given a positive integer n. The beauty factor of a number is the sum of digits obtained till the obtained sum is a single digit. you are given a beauty factor, b. your task is to find a minimum number (n) of length k whose beauty factor is b.


HackerEarth A beauty factor problem solution


HackerEarth A beauty factor problem solution.

#include<bits/stdc++.h>
#include<climits>

using namespace std;

bool check(vector<int> &a, int b) {
	while (a.size() > 1) {
		int sum = 0;
		for (int i = 0; i < a.size(); i++) {
			sum += a[i];
		}
		vector<int> b;
		while (sum > 0) {
			b.push_back(sum % 10);
			sum /= 10;
		}
		a = b;
	}
	return a[0] == b;
}

int main() {
	cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w" , stdout);
#endif
	int b , k;
	cin >> b >> k;
	string s = "123456789";
	string ans = "9999999999";
	for (int mask = 1; mask <= 512; mask++) {
		vector<int> v;
		for (int i = 0 ; i < 9; i++) {
			if (mask & (1 << i)) {
				v.push_back(s[i] - '0');
			}
		}
		vector<int> temp = v;
		if (v.size() == k && check(v, b)) {
			string s1 = "";
			for (int i = 0; i < temp.size(); i++) {
				s1 += to_string(temp[i]);
			}
			ans = min(ans, s1);
		}
	}
	if (ans == "9999999999") cout << "-1" << endl;
	else cout << ans << endl;
}

second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e9, maxd = 10;
char dp[maxn];
int ans[maxd][maxd] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{0, 19, 29, 12, 13, 14, 15, 16, 17, 18},
{0, 127, 128, 129, 139, 149, 123, 124, 125, 126},
{0, 1234, 1235, 1236, 1237, 1238, 1239, 1249, 1259, 1269},
{0, 12349, 12359, 12369, 12379, 12389, 12345, 12346, 12347, 12348},
{0, 123589, 123689, 123456, 123457, 123458, 123459, 123469, 123479, 123489},
{0, 1234567, 1234568, 1234569, 1234579, 1234589, 1234689, 1234789, 1235789, 1236789},
{0, 12345679, 12345689, 12345789, 12346789, 12356789, 12456789, 13456789, 23456789, 12345678},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 123456789}};
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int b, k;
    cin >> b >> k;
    cout << (ans[k][b] ? ans[k][b] : -1) << '\n';
    return 0;
    iota(dp, dp + 10, 0);
    for(int i = 10; i < maxn; i++){
        string s = to_string(i);
        int su = accumulate(s.begin(), s.end(), 0) - '0' * s.size();
        dp[i] = dp[su];
        sort(s.begin(), s.end());
        if(s[0] == '0' || unique(s.begin(), s.end()) != s.end())
            continue;
        if(!ans[s.size()][dp[i]])
            ans[s.size()][dp[i]] = i;
    }
    for(int i = 0; i < maxd; i++){
        cout << "{";
        for(int j = 0; j < maxd; j++)
            cout << ans[i][j] << ", ";
        cout << "},\n";
    }
}