expertcoderhk's blog

Intresting question on binary number
By expertcoderhk, history, 9 months ago, In English

Given a binary string of length<=100000, where even index means positive power of 2 and odd index means negative power of 2, find the value of string in normal binary representation.Assume rightmost index is least significant power.

For e.g If string s="1011" will be equal to (2^0)*1-(2^1)*1+(2^2)*0-(2^3)*1 = -9 so represent -9 in binary reprsentation How to approach this question.

  • Vote: I like it
  • -15
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

can you provide source?

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to find this question on online judges, but was not able to find any

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I doubt this is from an OA. Also not a hard problem for an expert atleast.

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please suggest how to solve this in optimal complexity?

        → Reply
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Sorry but I unintentionally don't want to help in an ongoing OA. I would answer this after awhile.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Its not a running OA, i heard it from my friends , and we had our OAS's last year, also have edited the question, decimal thing is easy , we need the string representation,

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
              ← Rev. 2   Vote: I like it +3 Vote: I do not like it

              What? This problem doesn't make sense then. Why do you specifically need string representation? I'm sure this isn't solvable for 1e5 length. You would have to use string multiplication and addition and surely that will take quite alot of time. 2^60 is around 1e18, there's no need to guess how big 2^1e5 would be).

              → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by expertcoderhk (previous revision, new revision, compare).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Final solution needs to be string not a decimal

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
In case you are still interested, I came up with this, can be altered to fix minor errors
→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Correct me if I am wrong, the problem is equivalent to finding the difference between numbers in which even bits are set and in which odd bits are set. So if we are given a string 10110101, we can divide this string into two strings -> 10100000 (if odd bits are set in the original string set that bit in this string) and 00010101 (if odd bits are set in the original string set that bit in this string) and we can simply find the difference between these two strings

→ Reply
»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Consider the more general problem of converting any binary number with negative digits into a normal binary number.

Observe that a chain of the form (1)(0)(0)...(0)(0)(-1) becomes (0)(1)(1)...(1)(1)(1).

So if we find the most significant -1 and the nearest more-significant 1, then we can remove that -1. Then just repeat until there are no more negatives. For example:

1. +1   0  -1  -1   0  +1  -1   = 64 - 16 - 8 + 2 - 1 = 41
2.  0  +1  +1  -1   0  +1  -1
3.  0  +1   0  +1   0  +1  -1
4.  0  +1   0  +1   0   0  +1   = 32 + 8 + 1 = 41
result: 0101001

This is pretty straightforward to implement in linear time:

// a[0] is the least significant digit
// a[i] is one of {-1, 0, +1}
vector<int> solve(vector<int> a) {
    int j = int(a.size()); // position of the last +1 we have seen
    for (int i = int(a.size()) - 1; i >= 0; --i) {
        if (a[i] == 1) {
            j = i;
        } else if (a[i] == -1) {
            for (int k = i; k < j; ++k)
                a[i] = 1;
            a[j] = 0;
            j = i;
        }
    }
    return a;
}

It doesn't work if the most significant digit is -1 (i.e. when the number is negative) but this is easy to detect and you can just flip the sign of all the digits and handle the negative however you want.

→ Reply