-2
$\begingroup$

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.

$\endgroup$
  • 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
2
$\begingroup$

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

$\endgroup$
  • $\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
-2
$\begingroup$

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.

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

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