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.


closed as unclear what you're asking by D.W., Rick Decker, David Richerby, Juho, Guy Coder Jul 8 '14 at 16:50

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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

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.

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

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.$$

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.