# paritioning a number into two sets based on sum of digits

• Feb 11th 2011, 05:40 PM
pranay
paritioning a number into two sets based on sum of digits
hi, how can one determine whether a number belongs to such a set of numbers whose every element can be divided into two sets such that the sum of digits of each set of the number is same.
E.g
23450 does belong to such a set , as it can be split into two sets : (3,4,0) and (2,5) such that sum of digits in each set is the same(7).
Similary 91125 belongs to such a set: (9) and (1,1,2,5).
but 567 , or 34523 do not belong to such a set of numbers .

By simple brute-force method it would take long timt to find such number among a range. So is there any better sollution to it? Maybe by usung bit operations?
Thanks.
• Feb 13th 2011, 02:43 AM
zzzoak
The main thing is to make from the given number a set of its digits.

$\displaystyle a_n \: 10^n+a_{n-1} \: 10^{n-1}+...+a_0 \; \to (a_n, \: a_{n-1}, \: ... \: ,a_0)$

This may be done :
1) find max n.
2) dividing the number by 10^i and subtracting from n to 1.