Topcoder SRM 509 DIV1 250

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]-'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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s