Given a number N, complete the following tasks,
Task 1. Generate a new number from N by changing the zeroes in the binary representation of N to 1.
Task  2. Find the difference between N and the newly generated number.
 
Example 1: 
Input: N = 8 
Output: 7 15
Explanation:
There are 3 zeroes in binary representation
of 8. Changing them to 1 will give 15.
Difference between these two is 7.
Example 2: 
Input: N = 6 
Output: 1 7
Explanation:
There is 1 zero in binary representation
of 6. Changing it to 1 will give 7.
Difference between these two is 1.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function changeBits() which takes an integer N as input parameter and returns a list of two integers containing the difference and the generated number respectively.
 
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)
 
Constraints:
0 <= N <= 10^{8}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def changeBits(self, N):

        # code here 

Solutions:
class Solution:

	def changeBits(self, N):
		import math
		a = int(math.log(N, 2) + 1)
		a = pow(2, a) - 1
		return (a - N, a)


import math

class Solution:

	def changeBits(self, N):
		b = str(bin(N).replace('0b', ''))
		d = ''
		for i in b:
			if i == '0':
				d += '1'
			else:
				d += i
		s = int(d, 2)
		b = []
		b.append(abs(N - s))
		b.append(s)
		return b


class Solution:

	def changeBits(self, N):
		if N == 1:
			return [0, 1]
		a = bin(N)[2:]
		for i in a:
			if i == '0':
				s = a.replace(i, '1')
		aa = int(s, 2)
		return [abs(aa - N), aa]


class Solution:

	def changeBits(self, N):
		old = bin(N)
		arr = list(old)
		a = []
		for i in range(2, len(arr)):
			if arr[i] == 0:
				a.append('1')
			else:
				a.append('1')
		ans = int('0b' + ''.join((x for x in a)), 2)
		diff = ans - N
		op = [diff, ans]
		return op


import math

class Solution:

	def changeBits(self, N):
		cnt = int(math.log2(N)) + 1
		ans = (1 << cnt) - 1
		return [ans - N, ans]


class Solution:

	def changeBits(self, N):
		p = N
		total = 0
		i = 0
		while N != 0:
			total += 2 ** i
			i += 1
			N = N >> 1
		return [total - p, total]


class Solution:

	def changeBits(self, N):
		if N == 0:
			return (-1, -1)
		n = N
		res = ''
		while N > 0:
			res += '1'
			N = N >> 1
		num = int(res, 2)
		return (num - n, num)


class Solution:

	def changeBits(self, N):
		s = ''
		list = []
		b = bin(N)
		sum = 0
		b1 = b[2:]
		for i in b1:
			if i == '0':
				s = s + '1'
			else:
				s = s + i
		p = 0
		sum = 0
		for j in s:
			b2 = int(j)
			sum = sum + b2 * pow(2, p)
			p = p + 1
		list.append(sum - N)
		list.append(sum)
		return list


class Solution:

	def changeBits(self, N):
		myList = []
		val = 1
		while True:
			if N <= val:
				break
			else:
				val = val * 2 + 1
		val = val
		myList.append(val - N)
		myList.append(val)
		return myList


class Solution:

	def changeBits(self, N):
		a = bin(N)[2:]
		b = '1' * len(a)
		c = int(b, 2)
		return [c - N, c]


class Solution:

	def changeBits(self, N):
		b = bin(N)
		d1 = str(b).replace('0', '1').replace('1b', '')
		c = int(d1, 2)
		return (c - N, c)


class Solution:

	def changeBits(self, N):
		bn = str(bin(N))
		n = '1' * (len(bn) - 2)
		nbn = int('0b' + n, 2)
		x = [nbn - N, nbn]
		return x


class Solution:

	def changeBits(self, N):
		a = bin(N)[2:]
		c = ''
		for i in a:
			if i == '1' or i == '0':
				c += '1'
		d = int(c, 2)
		return (abs(N - d), d)


class Solution:

	def changeBits(self, N):
		k = bin(N)[2:]
		s = k.replace('0', '1')
		return (int(s, 2) - N, int(s, 2))


class Solution:

	def changeBits(self, N):
		dn = N
		(s, x) = (0, 1)
		while dn != 0:
			if dn % 2 == 0 or dn % 2 == 1:
				s += x
			x = x * 2
			dn = dn >> 1
		return (s - N, s)


from math import log

class Solution:

	def changeBits(self, N):
		bits = int(log(N, 2)) + 1
		num = 1 << bits
		num -= 1
		return (num - N, num)


class Solution:

	def changeBits(self, N):
		if N == 0:
			return (-1, -1)
		a = bin(N)[2:]
		b = 2 ** len(a) - 1
		return (b - N, b)


class Solution:

	def changeBits(self, N):
		ln = 0
		a = N
		while a:
			ln += 1
			a = a >> 1
		return [(1 << ln) - 1 - N, (1 << ln) - 1]


class Solution:

	def changeBits(self, N):
		a = N
		b = bin(a)[2:]
		d = []
		c = ''
		for i in b:
			if i == '0':
				c += '1'
			else:
				c += i
		ans = int(c, 2)
		ss = abs(ans - a)
		d.append(ss)
		d.append(ans)
		return d


class Solution:

	def changeBits(self, N):
		for i in range(32):
			if N < 2 ** i:
				break
		m = 2 ** i - 1
		return [m - N, m]


class Solution:

	def changeBits(self, n):
		r = n
		i = 0
		s = 0
		while n:
			s += 2 ** i
			i += 1
			n = n // 2
		return [s - r, s]


from math import log2

class Solution:

	def changeBits(self, N):
		n = int(log2(N)) + 1
		x = (1 << n) - 1
		return (x - N, x)


from math import log2

class Solution:

	def changeBits(self, N):
		y = int('1' * int(log2(N)) + '1', 2)
		return [y - N, y]


class Solution:

	def changeBits(self, N):
		s = bin(N)
		g = s[2:]
		h = int('1' * len(g), 2)
		return (h - N, h)


class Solution:

	def changeBits(self, N):
		b = bin(N)[2:]
		p = int('1' * len(b), 2)
		t = abs(p - N)
		return (t, p)


class Solution:

	def changeBits(self, N):
		res = int(bin(N)[2:].replace('0', '1'), 2)
		return (res - N, res)


class Solution:

	def changeBits(self, N):
		a = bin(N).replace('0b', '')
		b = []
		a = a.replace('0', '1')
		a1 = int(a, 2)
		b.append(a1 - N)
		b.append(a1)
		return b


class Solution:

	def changeBits(self, N):
		g = N
		s = ''
		while g != 0:
			s += str(g % 2 ^ 1)
			g = g // 2
		s = s[::-1]
		k = int(s, 2)
		return [k, k ^ N]


class Solution:

	def changeBits(self, N):
		r = '{0:b}'.format(N)
		l = len(r)
		n = '1' * l
		a = int(n, 2)
		ans = [a - N, a]
		return ans


class Solution:

	def changeBits(self, num):
		li = []
		N = num
		while N:
			mod = N % 2
			li.append(mod)
			N = N // 2
		n = len(li)
		for i in range(n):
			if li[i] == 0:
				li[i] = 1
		value = pow(2, n) - 1
		return [value - num, value]


class Solution:

	def changeBits(self, N):
		totel_bits = 0
		num = N
		while N != 0:
			totel_bits = totel_bits + 1
			N = N >> 1
		maximum_num = 2 ** totel_bits - 1
		new_num = maximum_num - num
		return [new_num, maximum_num]


class Solution:

	def changeBits(self, n):
		return (int(bin(n)[2:].replace('0', '1'), 2) - n, int(bin(n)[2:].replace('0', '1'), 2))


class Solution:

	def changeBits(self, N):
		i = 0
		res = 0
		n = N
		while N:
			res += 2 ** i
			N >>= 1
			i += 1
		return [res - n, res]


class Solution:

	def changeBits(self, N):
		output = []
		bins = str(bin(N))
		bins = bins[2:].replace('0', '1')
		output.append(int(bins, 2))
		if N > int(bins, 2):
			k = 1
		else:
			k = -1
		output.append(k * (N - int(bins, 2)))
		return sorted(output)


class Solution:

	def changeBits(self, N):
		r = ''
		k = bin(N)[2:]
		for i in k:
			if i == '0':
				r += '1'
			else:
				r += i
		d = int(r, 2)
		t = d - N
		return [t, d]


import math

class Solution:

	def changeBits(self, N):
		N2 = (1 << int(math.log2(N)) + 1) - 1
		return [N2 - N, N2]


class Solution:

	def changeBits(self, N):
		res = []
		temp = N
		while N > 0:
			res.append(N % 2)
			N = int(N / 2)
		l = len(res)
		l = 2 ** l - 1
		return [abs(l - temp), l]


class Solution:

	def changeBits(self, n):
		t = n
		k = bin(n)[2:]
		s = ''
		for i in range(len(k)):
			if k[i] == '1':
				s += '0'
			else:
				s += '1'
		n = int(s, 2)
		return [n, n + t]


class Solution:

	def changeBits(self, N):
		og = ''
		copy = N
		while copy > 0:
			og += str(copy % 2)
			copy //= 2
		new = og.replace('0', '1')
		ans = 0
		for i in range(len(new)):
			ans += pow(2, i)
		return [ans - N, ans]


class Solution:

	def changeBits(self, N):
		n = list(bin(N)[2:])
		for i in range(len(n)):
			if n[i] == '0':
				n[i] = '1'
		return [abs(int(''.join(n), 2) - N), int(''.join(n), 2)]


class Solution:

	def changeBits(self, N):
		s = bin(N)[2:]
		a = ''
		for i in s:
			if i == '0':
				a += '1'
			else:
				a += i
		b = int(a, 2)
		return (abs(N - b), b)


class Solution:

	def changeBits(self, N):
		a = len(bin(N)[2:])
		a = 2 ** a - 1
		a = [a - N, a]
		return a


class Solution:

	def changeBits(self, N):
		count = 0
		n = N
		while n:
			count += 1
			n = n // 2
		i = 0
		new = 0
		while count:
			new += 1 << i
			count -= 1
			i += 1
		return [new - N, new]


class Solution:

	def changeBits(self, N):
		b = list(bin(N)[2:])
		for i in range(len(b)):
			if b[i] == '0':
				b[i] = '1'
		s = int(''.join(b), 2)
		return [s - N, s]


class Solution:

	def changeBits(self, N):
		m = bin(N)[2:]
		t = ''
		for i in m:
			if i == '0':
				t += '1'
			else:
				t += '1'
		v = int(t, 2)
		return [v - N, v]


class Solution:

	def changeBits(self, N):
		l = str(bin(N))[2:]
		a = l.replace('0', '1')
		return (int(a, 2) - N, int(a, 2))


class Solution:

	def changeBits(self, N):
		t = N
		c = 0
		while t:
			c += 1
			t //= 2
		res = 2 ** c - 1
		l = [res - N, res]
		return l


class Solution:

	def changeBits(self, N):
		p = ''
		s = len(str(bin(N))) - 2
		c = 0
		i = 0
		while s > 0:
			c += pow(2, i)
			i += 1
			s -= 1
		return [c - N, c]


class Solution:

	def changeBits(self, N):
		temp = N
		count = 0
		while temp:
			temp = temp >> 1
			count += 1
		new = (1 << count) - 1
		new = N | new
		return (new - N, new)


class Solution:

	def changeBits(self, N):
		a = bin(N)
		a = a[2:]
		b = '0b'
		for i in range(len(a)):
			if a[i] == '0':
				b += '1'
			else:
				b += a[i]
		b = int(b, 2)
		a = int(a, 2)
		difference = abs(a - b)
		res = []
		res.append(difference)
		res.append(b)
		return res


class Solution:

	def changeBits(self, N):
		tempN = N
		count = 0
		while tempN:
			tempN >>= 1
			count += 1
		all1s = 2 ** count - 1
		ans = [all1s - N, all1s]
		return ans


import math

class Solution:

	def changeBits(self, N):
		returnArr = []
		binaryStr = bin(N)[2:]
		binaryStrArr = list(binaryStr)
		for i in range(len(binaryStrArr)):
			if binaryStrArr[i] == '0':
				binaryStrArr[i] = '1'
		string = ''
		for data in binaryStrArr:
			string += data
		value = int(string, 2)
		returnArr.append(abs(N - value))
		returnArr.append(value)
		return returnArr


import math as m

class Solution:

	def changeBits(self, N):
		M = ''.join(['1' for i in range(0, len(bin(N)[2:]))])
		K = int(M, 2)
		return (K - N, K)


class Solution:

	def changeBits(self, N):
		temp = N
		cnt = 0
		while temp:
			cnt += 1
			temp >>= 1
		newNum = N | (1 << cnt) - 1
		return (newNum - N, newNum)


class Solution:

	def changeBits(self, N):
		b = int(bin(N).lstrip('0b').replace('0', '1'), 2)
		return [b - N, b]


class Solution:

	def changeBits(self, N):
		lis = []
		x = bin(N).replace('0b', '')
		a = x[0]
		x = x[1:]
		x = x.replace('0', '1')
		x = a + x
		dec = int(x, 2)
		res = abs(dec - N)
		lis.append(res)
		lis.append(dec)
		return lis


class Solution:

	def changeBits(self, N):

		def decimalToBinary(n):
			return bin(n).replace('0b', '')
		New_N = decimalToBinary(N)

		def Zero_to_one(N):
			tmp = ''
			for i in N:
				if i == '0':
					tmp = tmp + '1'
				else:
					tmp = tmp + i
			return tmp
		New_N = Zero_to_one(New_N)

		def binaryToDecimal(binary):
			decimal = 0
			fact = len(binary) - 1
			for i in binary:
				decimal = decimal + int(i) * 2 ** fact
				fact = fact - 1
			return decimal
		ans2 = binaryToDecimal(New_N)
		diff = ans2 - N
		ans = []
		ans.append(diff)
		ans.append(ans2)
		return ans


class Solution:

	def changeBits(self, N):
		a = bin(N)
		c = [i for i in a]
		c.pop(0)
		c.pop(0)
		d = 0
		e = 1
		for i in c:
			d += e
			e *= 2
		return (d - N, d)


class Solution:

	def changeBits(self, N):
		s = bin(N)
		s = s[2:]
		l = list(s)
		for i in range(len(l)):
			if l[i] == '0':
				l[i] = '1'
		s = ''
		for i in range(len(l)):
			s += l[i]
		k = len(l) - 1
		a = 0
		for i in range(k, -1, -1):
			a += int(s[i]) * 2 ** i
		m = []
		m.append(a - N)
		m.append(a)
		return m


class Solution:

	def changeBits(self, N):
		if N == 0:
			return (-1, -1)
		n = bin(N)[2:]
		n = n.replace('0', '1')
		num = 0
		for i in range(len(n)):
			num += 2 ** i
		return (num - N, num)


import math

class Solution:

	def changeBits(self, N):
		p = int(math.log(N, 2)) + 1
		return (2 ** p - 1 - N, 2 ** p - 1)


class Solution:

	def changeBits(self, N):
		a = '{0:b}'.format(N)
		b = a.replace('0', '1')
		c = str(b)
		d = int(c, 2)
		return (d - N, d)


from math import log2

class Solution:

	def changeBits(self, N):
		p = int(log2(N))
		m = 2 ** (p + 1) - 1
		n = N | m
		return (n - N, n)


class Solution:

	def changeBits(self, N):
		N1 = bin(N)[2:].replace('0', '1')
		return [abs(int(N1, 2) - N), int(N1, 2)]


class Solution:

	def changeBits(self, N):
		c = 0
		num = N
		while N > 0:
			N = N >> 1
			c += 1
		new = 2 ** c - 1
		return [new - num, new]


class Solution:

	def changeBits(self, N):
		c = 0
		p = N
		while N > 0:
			N = N >> 1
			c += 1
		no = 2 ** c - 1
		return [no - p, no]


class Solution:

	def changeBits(self, n):
		m = bin(n)
		l = len(m) - 2
		o = 2 ** l - 1
		return [o - n, o]


class Solution:

	def changeBits(self, N):
		binrep = self.decimaltob(N)
		newno = binrep.replace('0', '1')
		newnoint = int(newno, 2)
		diff = abs(N - newnoint)
		return [diff, newnoint]

	def decimaltob(self, n):
		return bin(n).replace('0b', '')

	def binarytodec(self, n):
		return int(n, 2)


class Solution:

	def changeBits(self, N):
		x = N
		s = 0
		result = []
		while x > 0:
			r = x % 2
			s = s + 1
			x = x // 2
		m = 2 ** s - 1
		op2 = m - N
		result.append(op2)
		result.append(m)
		return result


class Solution:

	def changeBits(self, N):
		bits = len(bin(N)[2:])
		ans = pow(2, bits) - 1
		sub = ans - N
		return [sub, ans]


class Solution:

	def changeBits(self, N):
		x = bin(N)[2:]
		s = ''
		l = []
		for i in x:
			if i == '0':
				s = s + '1'
			else:
				s = s + i
		x = int(s, 2)
		l.append(x - N)
		l.append(x)
		return l


class Solution:

	def changeBits(self, N):
		b = bin(N)[2:]
		while '0' in b:
			b = b.replace('0', '1')
		K = int(b, 2)
		return [abs(N - K), K]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, N):
		rem = 0
		b = 0
		t = 1
		tem = N
		c = 0
		while N > 0:
			rem = int(N % 2)
			N = int(N / 2)
			b = b + rem * t
			t = t * 10
			c += 1
		f = 2 ** c - 1
		tem = f - tem
		a = list()
		a.append(tem)
		a.append(f)
		return a
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


import math

class Solution:

	def changeBits(self, N):
		num = int(math.log(N) / math.log(2) + 1)
		next = 2 ** num - 1
		return [next - N, next]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, N):
		r = []
		m = bin(N)
		m = m[2:]
		m = m.replace('0', '1')
		m = int(m, 2)
		r.append(abs(m - N))
		r.append(m)
		return r
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, n):
		b = bin(n)
		b = b.replace('0b', '')
		s = 0
		for i in range(len(b)):
			s = s * 10 + 1
		s = str(s)
		s = int(s, 2)
		d = s - n
		return (d, s)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, N):
		l = []
		p = []
		h = 0
		s = 0
		c = 0
		num = bin(N)
		for i in num:
			if i == '0' and h == 0:
				i = '0'
				h = 1
			elif i == '0' and h != 0:
				i = '1'
			elif i == 'b':
				i = '0'
			else:
				i = '1'
			i = int(i)
			l.append(i)
		l = l[::-1]
		for j in l:
			if j == 1:
				s = s + 2 ** c
			c = c + 1
		p.append(abs(s - N))
		p.append(s)
		return p
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, n):
		m = n
		i = 0
		k = 0
		while n:
			if n & 1 == 0:
				k = k | 1 << i
			n = n >> 1
			i += 1
		return [k, m + k]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, N):
		n = ''
		tmp = N
		while tmp:
			if tmp & 1 == 0:
				n = str((tmp ^ 1) & 1) + n
			else:
				n = str(tmp & 1) + n
			tmp >>= 1
		n = int(n, 2)
		return [n - N, n]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, N):
		k = 0
		a = N
		while N:
			k += 1
			N = N >> 1
		b = 2 ** k - 1
		return [b - a, b]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, N):
		Nbin = bin(N).replace('0b', '')
		Nnew = Nbin.replace('0', '1')
		diff = int(Nnew, 2) - N
		return (diff, int(Nnew, 2))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.changeBits(N)
		print(ans[0], ans[1])


class Solution:

	def changeBits(self, N):
		h = bin(N)
		k = h[2:]
		n = len(k)
		m = ''
		ans = []
		for i in range(0, n):
			m = m + '1'
		j = int(m, 2)
		ans.append(j - N)
		ans.append(j)
		return ans


import math

class Solution:

	def changeBits(self, N):
		self.N = N
		k = self.N
		e = ''
		r = 0
		y = ''
		while self.N > 1:
			r = self.N % 2
			e += str(r)
			self.N = self.N // 2
		e += str(self.N)
		t = e[::-1]
		for j in range(0, len(t), 1):
			y += '1'
		o = len(y)
		sum = pow(2, o) - 1
		return (sum - k, sum)


class Solution:

	def changeBits(self, N):
		ansList = []
		newStr = ''
		x = bin(N)
		binary = x[2:]
		for i in binary:
			if i == '0':
				newStr += '1'
			else:
				newStr += i
		y = int(newStr, 2)
		ansList.append(y - N)
		ansList.append(y)
		return ansList