Sum of Digits

QUESTION

You are given an array of N distinct numbers. Now, we call the Digit Value of a number to be the sum of its digits.\n\nNow, a subset is a set of not-necessarily-contiguous array elements. We call the value of a set to be the the maximum over the Digit Value of all elements it contains.\n\nNow, you need to find the summation of the values of all 2^N -1 non-empty subsets of this array. As the answer can be rather large, print it Modulo 10^9+7. Can you do it ?\n\nInput Format :\n\nThe first line contains a single integer N. The next line contains N space separated integers, where the ith integer denotes A[i].\n\nOutput Format :\n\nPrint the summation of the value of each non-empty subset of the given array Modulo 10^9+7.\n\nConstraints :\n\n1<=N<=10^5\n\n0<=A[i]<=10^18.

ANSWER

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll mod =1000000007;
 
ll power(ll a,ll b){
	ll res=1;
	while(b>0){
		if(b&1) res =(res*a)%mod;
		a=(a*a)%mod;
		b/=2;
	}
	return res%mod;
}
 
ll invmod(ll a){
	return power(a,mod-2);
}
 
ll digitsum(long long num){
	long long rem, div;
	ll sumdigit=0;
	while(num > 0){
		rem = num%10;
		sumdigit = (sumdigit + rem)%mod;
		num /= 10;
	}
	return sumdigit%mod; 
}
 
int main(){
	ll n;
	cin>>n;
	long long number,prod;
	ll arr[n];
	for(int i=0;i<n;i++){
		cin>>number;
		arr[i]=digitsum(number);
	}
	sort(arr,arr+n);
	reverse(arr,arr+n);
	ll summ = 0,left;
	for(int i=0;i<n;i++){
		left = power(2,n-i-1) ; 
		summ = (summ + (arr[i]*left)%mod)%mod;
	}
	cout<<summ%mod<<endl;
	return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro