2’s Complement

Posted: 18 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Given a binary string of length ‘N’, find its 2’s complement.

A binary string contains only ‘0’ or ‘1’.
2’s complement is 1’s complement + 1.
For example, 2’s complement of 00000101 is 11111011.

Input format :

The first line of input contains an integer T denoting the number of test cases.
The next line contains a string of length N.

Output format :

For each test case, print the 2’s complement of the given string in a separate line.

Note :

You don’t have to print anything; it has already been taken care of. Just implement the given function. 

Constraints :

1 <= T <= 5
1 <= N <= 20

where ‘T’ is the total number of test cases, and N is the length of the string.

Time  Limit : 1sec
Approach 1

For 2’s complement :

  • Find one’s complement.
  • Traverse the one’s complement starting from LSB (least significant bit) and look for 0.
    • Flip all 1’s (change to 0) until we find a ‘0’. Finally, we will flip that first 0.
Try Problem