2’s Complement

Easy
0/40
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in companies
AdobePayPal

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

1
00000101

Sample Output 1 :

11111011

Explanation of the Sample Input 1:

1’s complement of 00000101 will be 11111010, adding 1 to it will give 11111011.

Sample Input 2 :

1
0

Sample Output 2 :

10
Hint

First, find the 1’s complement then add 1 to it.

Approaches (2)
Can we do this by finding 1’s complement first?

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.
Time Complexity

O(N), where N denotes the length of the string.
 

We are traversing the string twice. Therefore, the final time complexity is O(N + N) = O(N).

Space Complexity

O(N), where N denotes the length of the string.
 

Since we are creating strings to store 1’s and 2’s complement, the final space complexity is O(N).

Code Solution
(100% EXP penalty)
2’s Complement
Full screen
Console