HackerEarth Sum of sum of digits problem solution

In this HackerEarth Sum of sum of digits problem solution Monk likes math problems very much. His math teacher taught him about sum of digits of a number. He decided to experiment a little with them.

Given a number, he recursively finds the sum of its digits till it becomes a single digit number. He calls this as Digit-Value of a number "

It can be written as :

sumOfDigits(n):

    if n is a single digit number:

        return n

    else:

        x = sum of the digits of n

        return sumOfDigits(x)

After seeing his interest in this concept, his teacher gave him an interesting problem, that uses the above function defined by him. She gave him an array A of N different numbers. Then she asks him Q queries. In each query, he has to form a set of K numbers from the array and find the sum of Digit-Values of those K numbers. This sum is called the value of that set.

The queries are of the following type :

1 K : Monk must output the maximum value of a set of size K, that can be obtained, as described above.

2 K : Monk must output the minimum value of a set of size K, that can be obtained, as described above.

Monk needs your help to complete this task.

HackerEarth Sum of sum of digits problem solution.

#include <bits/stdc++.h>
using namespace std;

#define TRACE
#ifdef TRACE
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define TR(...)
#endif

typedef long long                LL;
typedef vector < int >           VI;
typedef pair < int,int >         II;
typedef vector < II >            VII;

#define MOD                      1000000007
#define EPS                      1e-12
#define N                        200100
#define PB                       push_back
#define MP                       make_pair
#define F                        first 
#define S                        second
#define ALL(v)                   v.begin(),v.end()
#define SZ(a)                    (int)a.size()
#define FILL(a,b)                memset(a,b,sizeof(a))
#define SI(n)                    scanf("%d",&n)
#define SLL(n)                   scanf("%lld",&n)
#define PLLN(n)                  printf("%lld\n",n)
#define PIN(n)                   printf("%d\n",n)
#define REP(i,j,n)               for(LL i=j;i<n;i++)
#define PER(i,j,n)               for(LL i=n-1;i>=j;i--)
#define endl                     '\n'
#define fast_io                  ios_base::sync_with_stdio(false);cin.tie(NULL)

#define FILEIO(name) \
  freopen(name".in", "r", stdin); \
  freopen(name".out", "w", stdout);
 
inline int mult(int a , int b) { LL x = a; x *= LL(b); if(x >= MOD) x %= MOD; return x; }
inline int add(int a , int b) { return a + b >= MOD ? a + b - MOD : a + b; }
inline int sub(int a , int b) { return a - b < 0 ? MOD - b + a : a - b; }
LL powmod(LL a,LL b) { if(b==0)return 1; LL x=powmod(a,b/2); LL y=(x*x)%MOD; if(b%2) return (a*y)%MOD; return y%MOD; }

int f(LL x) {
  if(x < 10) return x;
  string s = to_string(x);
  LL y = 0;
  for(char i : s)
    y += int(i-'0');
  return f(y);
}

LL a[N];
LL pref[N];
int main() {
  int n,q; SI(n); SI(q);
  assert(n <= int(1e5));
  assert(q <= int(1e5));
  set <LL> S;
  REP(i,1,n+1) {
    SLL(a[i]);
    assert(a[i] <= LL(1e18));
    assert(!S.count(a[i]));
    S.insert(a[i]);
  }
  REP(i,1,n+1) a[i] = f(a[i]);
  sort(a+1,a+n+1);
  REP(i,1,n+1) pref[i] = pref[i-1] + a[i];
  while(q--) {
    int t,k; SI(t); SI(k);
    assert(t >= 1 && t <= 2);
    assert(k >= 1 && k <= n);
    if(t == 1) 
      PLLN(pref[n] - pref[n-k]);
    else
      PLLN(pref[k]);
  }
  return 0;
}

Second solution

#include<bits/stdc++.h>
#define inf 1e18
#define ll long long
using namespace std;
int main()
{
   int n,q;
   cin>>n>>q;
   assert(n>=1 && n<=100000);
   assert(q>=1 && q<=100000);
   int dv[100005];
   map<ll,int>mp;
   for(int i=0;i<n;i++)
   {
      ll temp;
      cin>>temp;
      assert(!mp[temp]);
      mp[temp]++;
      assert(temp>=1 && temp<=inf);
      int ans;
      if(temp<10)ans=temp;
      while(temp>=10)
      {
         ll val=temp;ans=0;
         while(val)
         {
            ans+=val%10;
            val/=10;
         }
         temp=ans;
      }
      dv[i]=ans;
      //cout<<dv[i]<<"\n";
   }
   int pre[100005];
   sort(dv,dv+n);
   pre[0]=dv[0];
   for(int i=1;i<n;i++)
      pre[i]=pre[i-1]+dv[i];
   while(q--)
   {
      int type;
      int k;
      cin>>type>>k;
      assert(type==1 || type==2);
      assert(k>=1 && k<=n);
      if(type==1)
         (k==n)?cout<<pre[n-1]<<"\n":cout<<pre[n-1]-pre[n-(k+1)]<<"\n";
      else
         cout<<pre[k-1]<<"\n";
   }
   return 0;
}