# Sum of all binary numbers matching a pattern [closed]

Given $a_1, a_2, a_3, \dots,a_7$ where $a_i \in \{0,1\}$. How to calculate sum of all binary number of the form $$\over {1a_1a_2*a_3**a_4***a_5a_6a_7}$$

where $*$ represent the position of running digits.

I am thinking about a dynamic programming solution.

• Why dynamic programming? How do you think this problem can be decomposed and solved recursively? What is the general problem? – Raphael Jul 7 '14 at 12:13
• Is the \over line actually mean something? – Apiwat Chantawibul Jul 7 '14 at 13:12
• Can you given an example? This would clarify whether $\ast$ stand for a bit, or they stand for either a bit or nothing. – Yuval Filmus Jul 7 '14 at 18:24

For any such pattern with $i$ stars we have to add $2^i$ numbers. Thus for the contribution of the fixed digits, we can replace the stars by $0$'s and append $i$ $0$'s at the right. For the contribution of the stars, we can replace the fixed digits by $0$'s and the stars by $1$'s and append $i-1$ $0$'s at the right.

For the specific example this gives $$~~~~1a_1a_2~0~~a_30~0\,~a_4~0~~0~~0~a_5a_6a_7000000~\\ + ~~~~~~~~~~~~~~~~1~0~1~\,1\,~~0~~1\,~\,1\,~1~~0~~0~000000~\\ = 1a_1a_2a_3\overline{a_3}a_4\overline{a_4}\overline{a_4}a_5\overline{a_5a_5a_5}a_6a_7000000.$$

• What if OP mean $*$ can be 0, 1 or null – Xeing Jul 7 '14 at 15:05
• I applaud this respond is fast and look promising. But the question in its current form is rather unclear. – Apiwat Chantawibul Jul 7 '14 at 15:36

If $*$ mean $0, 1$ or no digit: I write a very simple program (sorry, I have trouble with SHIFT + 8 and don't want Crtl + V too much :) )

int main(){
string s;
int res = 1, pos = 1;
cin >> s;
for(int i = 1; i < (int) s.length(); ++i){
if (s[i] == '0'){
res <<= 1; // res = 2 x res;
} else if (s[i] == '1'){
res <<= 1;
res += pos;
} else {
(res <<= 2) += (res >> 2) + pos;
(pos <<= 1) += (pos >> 1);
}
}
cout << res;
}


I will post the proof later. I need to sleep first.

• Please do post the proof and please replace this C++ implementation with pseudocode. – David Richerby Jul 7 '14 at 17:12