You are given a binary string S. You need to transform this string into another string of equal length consisting only of zeros, with the minimum number of operations.
A single operation consists of taking some prefix of the string S and flipping all its values. That is, change all the 0s in this prefix to 1s, and all the 1s in the prefix to 0s. You can use this operation as many number of times as you want over any prefix of the string.

-----Input-----
The only line of the input contains the binary string,  S . 

-----Output-----
Output a single line containing one integer, the minimum number of operations that are needed to transform the given string S into the string of equal length consisting only of zeros.

-----Constraints-----
- 1 ≤ |S| ≤ 100,000

-----Subtasks-----
- Subtask #1 (30 points): 1 ≤ |S| ≤ 2000
- Subtask #2 (70 points): Original constraints.

-----Example-----
Input:
01001001

Output:
6

-----Explanation-----
For the given sample case, let us look at the way where we achieved minimum number of operations.

Operation 1: You flip values in the prefix of length 8 and transform the string into 10110110 
Operation 2: You flip values in the prefix of length 7 and transform the string into 01001000 
Operation 3: You flip values in the prefix of length 5 and transform the string into 10110000 
Operation 4: You flip values in the prefix of length 4 and transform the string into 01000000 
Operation 5: You flip values in the prefix of length 2 and transform the string into 10000000 
Operation 6: You flip values in the prefix of length 1 and finally, transform the string into 00000000

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
s=input()
s1=s[::-1]
arr=[]
cnt=0
for i in range(len(s1)):
 arr.append(s1[i])
for i in range(len(arr)):
 if(arr[i]=="1"):
  for j in range(i,len(arr)):
   if(arr[j]=="1"):
    arr[j]="0"
   else:
    arr[j]="1"
  cnt+=1
print(cnt)

# cook your dish here
def rev(s):
 s1=''
 for i in s:
  if(i=='0'):
   s1=s1+'1'
  else:
   s1=s1+'0'
 return s1 
s=input()
s1=''
c=0
for i in range(len(s)-1,-1,-1):
 if(s[i]=='1'):
  s1=rev(s[:i])
  c=c+1
  s=s1

print(c) 

# cook your dish here
try:
 s=input()
 c=0
 for i in range(len(s)-1):
  if(s[i]!=s[i+1]):
   c=c+1
 if(s[-1]=='1'):
  print(c+1)
 else:
  print(c)
except:
 pass

n = input()
cnt = 0
x = n[0]
for i in range(len(n)):
 if(n[i] != x):
  cnt += 1
  x = n[i]
if n[-1]=='1':
 print(cnt+1)
else:
 print(cnt)

n = input()
if(set(n)=={'0'}):
 print(0)
else:
 cnt = 0
 x = n[0]
 for i in range(len(n)):
  if(n[i] != x):
   cnt += 1
   x = n[i]
 if n[-1]=='1':
  print(cnt+1)
 else:
  print(cnt)

def main():
 rev_s=reversed(input())
 flips=0
 flipped=False
 for b in rev_s:
  if b=='0':
   if not flipped:
    continue
   else:
    flipped=False
    flips+=1
    continue
  else:
   if flipped:
    continue
   else:
    flipped=True
    flips+=1
    continue
 print(flips)
main()

# cook your dish here
l=input()
cnt=0
n=len(l)
for i in range(n-1):
 if(l[i]!=l[i+1]):
  cnt+=1
if(l[-1]=='1'):
 cnt+=1
print(cnt)

t=1
for n in range(t):
 s=input()
 count=1
 for i in range(1,len(s)):
  if(s[i]!=s[i-1]):
   count+=1
 if(s[len(s)-1]=='0'):
  count-=1
 print(count)

# cook your dish here
S=str(input())
a=[]
for i in S:
 a.append(i)
c=0
for i in range(len(a)-1,-1,-1):
 if a[i]=='1':
  for k in range(0,i+1):
   if a[k]=='1':
    a[k]='0'
   else:
    a[k]='1'
  c=c+1
print(c) 

# import sys 
# sys.stdin = open('input.txt', 'r')  
# sys.stdout = open('output.txt', 'w')

s = input()
arr = []
n = len(s)
i = 0

while (i<n):
 x = s[i]
 while (i<n and s[i]==x):
  i += 1
 arr.append(x)

m = len(arr)
if (arr[0] == "0"):
 if (m==1):
  print(0)
 else:
  print((m//2)*2)
else:
 if (m&1==1):
  print((m//2)*2 + 1)
 else:
  m -= 1
  print((m//2)*2 + 1)

# cook your dish here
t=1
for _ in range(t):
 a=input()
 # x=s[0]
 count=1
 for i in range(1,len(a)):
  if(a[i]!=a[i-1]):
   count+=1
 # print("hbk",count)
 if(a[len(a)-1]=='0'):
  count-=1
 print(count)

# cook your dish here
s=input()
s=list(s)
n,c=0,0

j=0
while(n!=1):
 j+=1
 
 p=-1
 for i in range(len(s)-2,-1,-1):
  if(j%2!=0):

   if(s[i]=='0'):
    p=i
    break
  else:
   
   if(s[i]=='1'):
    p=i
    break
   
 if(p!=-1):
  c+=1
 
 s=s[0:p+1]
 
 if(len(s)==1) or (len(s)==0):
  n=1
 
 
print(c+1)