PROBLEM LINK:
Practice contest
Author: maazbinasad3
Tester: prasoonjain006
Editorialist: salik_anwer
DIFFICULTY:
Easy-Medium
PREREQUISITES:
String, Binary numbers
PROBLEM:
You are given a string, S that is a binary representation of a decimal number. This binary string can also be the representation of an excessively large number. This means more than 64 bits can be used to represent this number. You can do the following operation any number of times:
- Choose a character and flip it. This means, if the character is ‘1’, make it ‘0’ and vice versa.
Find minimum number operations needed to decrement the decimal representation of this number by 1.
QUICK EXPLANATION:
Find minimum number of bits to be inverted in a given binary representation for a decimal in order to decrement binary representation for the decimal by 1.
EXPLANATION:
- Find length of string, n.
- Traverse the string from the end.
- To decrement the binary representation by one, change all ‘0’ to ‘1’ till the first occurrence of ‘1’, change the first ‘1’ to ‘0’.
Leave the rest of the binary code as it is. - To get the number of operations required for this, count number of bits from the end of string till the first occurrence of ‘1’.
- Print the number of bits.
TIME COMPLEXITY:
O(N)
SOLUTION:
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–)
{
string S;
cin>>S;
int n = S.length();
int count = 0;
for(int i=n-1; i>=0; i–)
{if(S[i]==‘1’)
{
count++;
break;
}
else
{
count++;
}
}
cout<<count<<endl;
}
return 0;
}
Do share and discuss different approaches for the problem here. 