[leetcode][1009] Complement of Base 10 Integer

문제 : https://leetcode.com/problems/complement-of-base-10-integer/

 

---

6 - 0
3 - 1
1 - 1
0 - 1

N을 6이라 했을 때, 2진수는 1110이다. 따라서 보수는 0001이 된다.

N을 2로 나눈 나머지 값이 0이면 1을 1이면 0을 해당 자리 수 값에 곱해서 정답에 더한다.

N이 0인 경우 보수는 1이므로 이 때는 예외처리했다.

시간 복잡도는 O(logN).

 

+

N = 5(101) 일 때, 1의 보수를 구해보자.

1000 - 101 = 011 

011 - 1 = 010

2진수의 비트수는 log2(N)으로 구할 수 있다. 

예를 들어 N = 5(101) 일 때, log2(5) = 2.32193. 이에 +1을 한 뒤 정수로 바꿔주면 3이 된다. 이제 1에 3만큼 왼쪽 비트를 이동시켜주면 

1000 이 된다. 이 수에 101 을 뺀 뒤 1을 또 빼면 1의 보수인 010이 나온다.

시간복잡도는 O(1)

---

 

소스코드

https://gist.github.com/fpdjsns/a2f5812d1218065e20539f6cab6843ee

https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1009.%20Complement%20of%20Base%2010%20Integer.cpp