Some of us were having some discussion about posting some
challenge question for the community to participate in. This way
people could learn from the more experienced person's solution.

Here is the question that :

Intro :

A multiplied Sum Of digits is the sum of the digits of a number
N, in which those those sum of digits, are then multiplied of digits.

An example :

Let N = 12345;
SumOfDigits = 1 + 2 + 3 + 4 + 5 = 15;
Multiplied Sum of Digits = 1 * 5 = 5;
Problem Statement : Find the multiplied Sum Of digits of The number
N. Where N equals to the sum of the number from [ 2^0 , 2^50]

Example run :

N = The sum of the numbers from [2^0, 2^4] = 1+2+4+8+16 = 31
The sum of the Digits of N = 3 + 1 = 4;
The multiplied sum of digits of N = 4

[EDIT]

Guides :

4) Make it pure C++ since this is a C++ forum
5) Try to make it more portable as possible
6) Post code Here I guess
7) Do not post questions or anything else except solutions here.
8) PM me if something is unclear or you have a question, so I can fix the question or answer yours.

Merry Christmas.
[/EDIT]

Edited by firstPerson: n/a

5
Contributors
8
Replies
9
Views
8 Years
Discussion Span
Last Post by firstPerson

For some really big challenges designed for people of all experience levels see Sane's Monthly Algorithm Challenges here. I have made the three most recent challenges stickies so that they can be easily found.

Frankly, I did not understand the statement of the problem. The more I read it the more contradictory it looks. Maybe I shall quit drinking.

Can you please translate the following

A multiplied Sum Of digits is the sum of the digits of a number N, in which those those sum of digits, are then multiplied of digits.

into English so that a drunk Russian may understand?

LOL :)

Frankly, I did not understand the statement of the problem. The more I read it the more contradictory it looks. Maybe I shall quit drinking.

Can you please translate the following

into English so that a drunk Russian may understand?

Sorry for the unclarity.

A multiple sum of digits, is a number N, where N is the multiplied
of the individual digits of a number M, where M is the sum of the
digits of a number O.

For example:

In the problem above, first find a number O, where O is the sum
of numbers from 2^0 to 2^50.

For now assume the sum of the numbers from 2^0 to 2^50 is 123456789. Then next, you need to find the sum of the digits of those number.

The sum of the digits of the number, 123456789 is = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45.

Now the multiplied sum of digits is the multiplication of the individual
digits that consists in the sum of digits. Since the sum of the digits
we found is 45. The multiplied sum of digits is the multiplication
of the individual digits, so its = 4*5 = 20.

Therefore the multiplied sum of digits from the number 2^0 to 2^50
is 20.

Hope that was a bit clearer.

>Sorry for the unclarity
Here's a brute force example program that does what I think you're asking for. It might help the requirements become more clear for the participants (assuming I understand them ;)):

#include <functional>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

class listall {
const std::vector<int>& _list;
const std::string& _sep;
public:
listall ( const std::vector<int>& list, const std::string& sep = ", " )
: _list ( list ), _sep ( sep )
{}

friend std::ostream& operator<< ( std::ostream& out, const listall& obj )
{
out<<'[';

for ( std::vector<int>::size_type i = 0; i < obj._list.size(); i++ )
out<< obj._list[i] << ( i < obj._list.size() - 1 ? obj._sep : "" );

return out<<']';
}
};

std::vector<int> get_digits ( int n )
{
std::vector<int> v;

while ( n != 0 ) {
v.insert ( v.begin(), n % 10 );
n /= 10;
}

return v;
}

int main()
{
int n;

std::cout<<"Enter a number: ";

if ( std::cin>> n ) {
std::vector<int> ndigits = get_digits ( n );
int sum = std::accumulate (
ndigits.begin(), ndigits.end(), 0, std::plus<int>() );
std::vector<int> sumdigits = get_digits ( sum );
int product = std::accumulate (
sumdigits.begin(), sumdigits.end(), 1, std::multiplies<int>() );

std::cout<< n <<" = "<< listall ( ndigits, " + " ) <<" = "
<< sum <<" = "<< listall ( sumdigits, " * " ) <<" = "
<< product <<'\n';
}
}

Though an unconditional product might be confusing due to zero digits.

Edited by Narue: n/a

>> assuming I understand them

Yes, but instead of asking the user for the number N; N has to be
the sum from 2^0 -> 2^50. I though the instructions were clear enough,
especially with the examples.

>> assuming I understand them

Yes, but instead of asking the user for the number N; N has to be
the sum from 2^0 -> 2^50. I though the instructions were clear enough,
especially with the examples.

I think it would be clearer if you stated that what is to be inputted is an exponent. Sample runs:

Enter an exponent : 4

1 + 2 + 4 + 8 + 16 = 31
Sum of digits in 31 = 3 + 1 = 4
Product of digits in 4 = 4
Enter an exponent : 6

1 + 2 + 4 + 8 + 16 + 32 + 64 = 127
Sum of digits in 127 = 1 + 2 + 7 = 10
Product of digits in 10 = 1 * 0 = 0
Enter an exponent : 7

1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255
Sum of digits in 255 = 2 + 5 + 5 = 12
Product of digits in 12 = 1 * 2 = 2
Enter an exponent : 8

1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 = 511
Sum of digits in 511 = 5 + 1 + 1 = 7
Product of digits in 7 = 7

The grammar of the statement problem needs to be much more precise. People need to be told explicitly what is expected as input and what the output should be for that input.

>> assuming I understand them

Yes, but instead of asking the user for the number N; N has to be
the sum from 2^0 -> 2^50. I though the instructions were clear enough, especially with the examples.

So the missing link in Narue's code is the summation?
The sum itself is equal to 2^51 - 1. Assuming one decimal digit per byte a) we'd need 15 bytes or so to represent it; b) the Least Significant Digit (*) of 2th power is not zero hence subtraction of 1 is trivial; c) we just need a way to calculate a power of 2.
We can do it in a most straightforward way by means of multiply-by-two method:

int mul2(char * value, int len)
{
int i, carry;
for(i = 0, carry = 0; i < len; i++) {
value[i] = 2 * value[i] + carry;
if(value[i] >= 10) {
value[i] -= 10;
carry = 1;
} else {
carry = 0;
}
}
if(carry == 1) {
value[len] = 1;
len += 1;
}
return len;
}

and call it as in

char data[20] = { 1 }; // "fifteen bytes or so"
int i, len = 1;
for(i = 0; i < exponent; i++) {
len = mul2(data, len);
}

This works, although for large exponents is highly inefficient. Which leads us to the next challenge:
Write a program which given an exponent N, designs an optimal plan of calculating N'th power.

(*) For the record, I didn't abbreviate this.

Edited by nezachem: n/a

>>This works, although for large exponents is highly inefficient. Which leads us to the next challenge:
Write a program which given an exponent N, designs an optimal plan of calculating N'th power.

I think you should start a new thread if you wan't to purpose a different
problem.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.