HackerEarth Digit cube problem solution

In this HackerEarth Digit cube problem solution Let n be an integer. We define a function f(n) which returns the cube of the sum of digits of n.

You are given two integers n and k. You have to find the value of the integer that is returned when the function is recursively applied k times on n. Formally, you have to find the value of fk(n).


hackerEarth Digit cube problem solution

HackerEarth Digit cube problem solution.

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define c(P) cout<<P<<"\n"
#define sz(a) (ll)(a.size())

using namespace std;


const ll N = 500005;
const ll mod = 1e9 + 7;
vector<ll> v[150];

ll f(ll n){

ll c = 0;

while(n>0){
c += n%10;
n/=10;
}
return c;
}

void solve(){

ll x=0,y=0,c=0,ans=0;
ll n,m,k;
cin>>n >> k;
assert(n>=1 and n<=1e15);
assert(k>=1 and k<=1e15);

x = f(n);
m = sz(v[x]);

if(m>k){
c(v[x][k-1]);
return;
}
if(m==1){
c(v[x][0]);
return;
}

k -= (m -2);
k%=2;
c(v[x][m-k-1]);

}

signed main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,x,c;

for (ll i = 1; i <140; ++i){
n = i*i*i;
c =0;
std::set<ll> s;
s.insert(n);
v[i].pb(n);

while(true){
x = f(n);
v[i].pb(x * x * x);

if(s.find(x * x * x)!=s.end()){
break;
}
s.insert(x*x*x);
n = x * x * x;
}
}


int T;cin >> T;
assert(T>=1 and T<=1e6);

while (T--)
solve();

return 0;
}

second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAX_N = 3e6 + 14, LOG = 50, MAX_S = 136;

int sum_of_digits(ll n) {
string str = to_string(n);
return accumulate(str.begin(), str.end(), 0) - '0' * str.size();
}

int nxt[MAX_S][LOG];

int main() {
ios::sync_with_stdio(0), cin.tie(0);
for (int k = 0; k < LOG; ++k) {
for (int i = 1; i < MAX_S; ++i) {
if (k)
nxt[i][k] = nxt[nxt[i][k - 1]][k - 1];
else
nxt[i][0] = sum_of_digits(i * i * i);
}
}
int t;
cin >> t;
while (t--) {
ll n, k;
cin >> n >> k;
k--;
n = sum_of_digits(n);
for (int i = LOG - 1; i >= 0; --i)
if (k >> i & 1)
n = nxt[n][i];
cout << n * n * n << '\n';
}
}


Post a Comment

0 Comments