Question

Microsoft | OA Coding Questions and Solutions | Set - 79 | 2022 | Senior SDE

Answer 1

Q: Given a binary string of 0s and 1s, you need to make integer converted string to zero.
you are allowed to make the following operation

 

1. If n is odd then subtract 1 from the number
2. If n is even, then divide the n by 2

 

We need to find the minimum number of operations to make the string as 0.

 

Constraints:
Length of binary string = 1e6

 

int solution(string s) {
   int ans = 0;
   int start = 0;
   int n = s.size();
   while (start < n && s[start] == '0') {
      ++start;
   }
   int end = s.size() - 1;
   while (start <= end) {
      if (s[end] == '1') {
         ++ans;
      }
      --end;
      ++ans;
   }
   return ans - 1;
}