0
$\begingroup$

I am trying to understand and implement Bit flipping algorithm

Can someone share the psuedocode for the algorithm and explain in detail? I cannot understand the answer.

I also want to understand what topic this question falls under (like Dynamic Programming or Optimization).

$\endgroup$
  • $\begingroup$ @Ross Millikan Can you answer this question? Thank you. $\endgroup$ – pooja kosala Oct 13 '18 at 21:02
  • $\begingroup$ @TSR Can you answer this question? Thank you. $\endgroup$ – pooja kosala Oct 13 '18 at 21:02
  • $\begingroup$ @Ethan Bolker Can you answer this question? Thank you. $\endgroup$ – pooja kosala Oct 13 '18 at 21:02
0
$\begingroup$

The answer was saying to build up the string of all $1$ incrementally from the beginning: to have first bits $1$, then to have first two bits $1$, ..., then to have the first $n-k+1$ bits all in $1$.

The algorithm is that if the first $i-1$ bits are all $1$ and the $i$th bit is $0$ (where $1 \le i \le n-k+1$), then flip the bits from $i$ to $i+k-1$ inclusive will make at least the first $i$ bits all $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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