# PROBLEM STATEMENT

In a nutshell, Given a number X, we need to find ( Supersum(X) ) % 9.

Supersum(x):

Supersum of x is sum of all subsets of the number x.

Eg: 123, the subsets are {1, 2, 3, 12, 13, 23,123}

Supersum(123) = 1+2+3+12+13+23+123 = 177 % 9 = 6

You can find a detailed problem description here.

# SOLUTION

Breaking down the problem:

In the problem we need to find the number modulo 9.

Eg: 123 can be represented as (1*100+2*10+3)%9

By Modular Arithmetic,

we can simply to ( 1*(100%9) + 2*(10%9) + 3 ) % 9. The final answer is simply ( 1 + 2 + 3 ) % 9.

For Example 123,

Supersum(123) = 1 + 2 + 3 + (12%9) + (13%9) + (23%9) + (123%9)

It can be simplified to

Supersum(123) =  ( 1 + 2 + 3 + ( 1 + 2 ) + ( 1 + 3 ) + ( 2 + 3 ) + ( 1 + 2 + 3 ) ) % 9

Since Supersum contains all the subsets of a number, each digit appears for 2^n-1 , where n – no. of digits in the number

So, finally

Supersum(123) =  ( 1*4 + 2*4 + 3*4) % 9 = 6

# CODE

```class LuckyRemainder {
public:
int getLuckyRemainder(string X) {

if( X.size() == 1 )
return (X-'0')%9;

int mod = 1,i,sz=X.size();
int res = 0;
for(i=0;i<sz;i++)
res = (res + (X[i]-'0'))%9;

for(i=1;i<sz;i++)
mod = (mod*2)%9;

return ( res * mod ) % 9;

}

};

```
Advertisements