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


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