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