Given n and k, Construct a palindrome of size n using the binary representation of the number k.To construct the palindrome you can use the binary number of size k as many times as you wish and also you can trim all the  zeros from the end.The palindrome must always begin with 1 and contains the maximum number of zeros.
 
Example 1 :
Input : n = 5, k = 6
Output : 11011
Explanation: Binary representation of 6 is
110.After combining 110
twice and trimming the extra 0 in 
the end we get 11011
Example 2:
Input: n = 5, k = 8
Output: 10001
Explanation: Binary representation of 8 is
1000.After combining 1000 twice and trimming
the extra 0 in the end we get 10001.
Your Task:
You don't need to read or print anything. Your task is to complete the function binaryPalindrome() that takes two integers n, k and return a string of size n.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ k ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Graph algorithms

Graph traversal

String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def binaryPalindrome (self, n, k) : 

        #Complete the function



Solutions:
class Solution:

	def construct_answer(self, ans, arr, connected_zero_set):
		for i in range(len(arr)):
			if arr[i] in connected_zero_set:
				ans[i] = 1
		return ''.join((str(element) for element in ans))

	def binaryPalindrome(self, n, k):
		arr = [0 for i in range(n)]
		ans = [0 for i in range(n)]
		connected_zero_set = set([0])
		for i in range(n):
			arr[i] = i % k
		for i in range(n):
			if arr[i] in connected_zero_set:
				connected_zero_set.add(arr[-i - 1])
			if arr[-i - 1] in connected_zero_set:
				connected_zero_set.add(arr[i])
		return self.construct_answer(ans, arr, connected_zero_set)


class Solution:

	def dfs(self, parent, ans, connectChars):
		ans[0] = 1
		for linked_k_i in connectChars[0]:
			ans[linked_k_i] = 1

	def binaryPalindrome(self, n, k):
		arr = [0 for i in range(n)]
		ans = [0 for i in range(n)]
		connectChars = [[] for i in range(k)]
		for i in range(n):
			arr[i] = i % k
		for i in range(n):
			connectChars[arr[i]].append(arr[n - i - 1])
			connectChars[arr[n - i - 1]].append(arr[i])
		self.dfs(0, ans, connectChars)
		s = ''
		for i in range(n):
			if ans[arr[i]] == 1:
				s = s + '1'
			else:
				s = s + '0'
		return s


class Solution:

	def binaryPalindrome(self, n, k):
		arr = ['0' if i % k else '1' for i in range(n)]
		for i in range(n):
			if arr[i] == '1':
				arr[n - i - 1] = '1'
		output = ''
		for i in arr:
			output += i
		return output


class Solution:

	def dfs(self, u, connect_chars, visited):
		visited[u] = 1
		for v in connect_chars[u]:
			if visited[v] == 0:
				self.dfs(v, connect_chars, visited)

	def binaryPalindrome(self, n, k):
		pos_arr = [0] * n
		for i in range(n):
			pos_arr[i] = i % k
		connect_chars = {u: [] for u in range(k)}
		for i in range(n // 2):
			u = pos_arr[i]
			v = pos_arr[n - 1 - i]
			connect_chars[u].append(v)
			connect_chars[v].append(u)
		visited = [0] * k
		self.dfs(0, connect_chars, visited)
		res = ''
		for i in range(n):
			if visited[pos_arr[i]] == 1:
				res += '1'
			else:
				res += '0'
		return res


from bisect import bisect_left

class Solution:

	def binaryPalindrome(self, n, k):
		arr = ['0' for i in range(n)]
		for i in range(0, n, k):
			arr[i] = arr[n - i - 1] = '1'
		return ''.join(arr)


class Solution:

	def binaryPalindrome(self, n, k):
		output = ['0' for i in range(n)]
		base = ['0' for i in range(k)]
		out = 0
		if k >= n:
			output[0] = '1'
			output[-1] = '1'
			output = ''.join(output)
			return int(output)
		else:
			rem = n % k
			if rem == 0:
				base[0] = '1'
				base[-1] = '1'
			else:
				base[0] = '1'
				base[rem - 1] = '1'
		count = 0
		for i in range(n):
			count = count % k
			output[i] = base[count]
			count += 1
		out = ''.join(output)
		return int(out)


class Solution:

	def binaryPalindrome(self, n, k):
		a = [0] * n
		r = []
		c = [[] for i in range(k)]
		if k == 1:
			return str(k) * n
		for i in range(n):
			a[i] = i % k
		t = [0] * k
		for i in range(int(n / 2)):
			c[a[i]].append(a[n - i - 1])
			c[a[n - i - 1]].append(a[i])
		for i in range(n // k + 1):
			self.dfs(0, t, c)
			r.extend(t)
			t = [0] * k
		r = r[:n]
		for i in range(n):
			r[i] = str(r[i])
		return ''.join(r)

	def dfs(self, p, ans, c):
		ans[p] = 1
		for i in range(len(c[p])):
			if ans[c[p][i]] != 1:
				self.dfs(c[p][i], ans, c)


class Solution:

	def binaryPalindrome(self, n, k):
		ans = [0] * n
		arr = [0] * n
		graph = [set() for i in range(k)]
		for i in range(n):
			arr[i] = i % k
		for i in range(n // 2):
			graph[arr[i]].add(arr[n - i - 1])
			graph[arr[n - i - 1]].add(arr[i])

		def dfs(node):
			ans[node] = 1
			for child in graph[node]:
				if ans[child] == 0:
					dfs(child)
		dfs(0)
		return ''.join([str(ans[arr[i]]) for i in range(n)])


import math

class Solution:

	def binaryPalindrome(self, n, k):
		if n == 1:
			return '1'
		if n <= k:
			return '1' + '0' * (n - 2) + '1'
		if k == 1:
			return '1' * n
		last_zeros = k - n % k
		if last_zeros == k:
			k_str = '1' + '0' * (k - 2) + '1'
		elif last_zeros == k - 1:
			k_str = '1' + '0' * last_zeros
		elif last_zeros == k - 2:
			k_str = '1' + '1' + '0' * last_zeros
		else:
			k_str = '1' + '0' * (k - 2 - last_zeros) + '1' + '0' * last_zeros
		s = k_str * int(math.ceil(n / k))
		return s[:n]


class Solution:

	def dfs(self, temp, result, charsjoin):
		result[temp] = 1
		for i in range(len(charsjoin[temp])):
			if not result[charsjoin[temp][i]]:
				self.dfs(charsjoin[temp][i], result, charsjoin)

	def binaryPalindrome(self, n, k):
		result = [0] * n
		arr = [0] * n
		charsjoin = [[] for i in range(k)]
		for i in range(n):
			arr[i] = i % k
		for i in range(int(n / 2)):
			charsjoin[arr[i]].append(arr[n - i - 1])
			charsjoin[arr[n - i - 1]].append(arr[i])
		self.dfs(0, result, charsjoin)
		ans = ''
		for i in range(n):
			ans += str(result[arr[i]])
		return ans


class Solution:

	def binaryPalindrome(self, n, k):

		def dfs(parent, ans, connectchars):
			ans[parent] = 1
			for i in connectchars[parent]:
				if not ans[i]:
					dfs(i, ans, connectchars)
		arr = [0] * n
		ans = [0] * n
		connectchars = [set() for i in range(k)]
		for i in range(n):
			arr[i] = i % k
		for i in range(int(n / 2)):
			connectchars[arr[i]].add(arr[n - i - 1])
			connectchars[arr[n - i - 1]].add(arr[i])
		dfs(0, ans, connectchars)
		return ''.join([str(ans[arr[i]]) for i in range(n)])


class Solution:

	def binaryPalindrome(self, n, k):
		arr = ['0'] * n
		arr[0] = arr[-1] = '1'
		for i in range(1, n):
			if i % k == 0:
				arr[i] = '1'
		i = 0
		j = n - 1
		while i < j:
			if arr[i] == '1':
				arr[j] = '1'
			elif arr[j] == '1':
				arr[i] = '1'
			i += 1
			j -= 1
		return ''.join(arr)


class Solution:

	def dfs(self, node, ans, adj):
		ans[node] = 1
		for k in adj[node]:
			if not ans[k]:
				self.dfs(k, ans, adj)
		return None

	def binaryPalindrome(self, n, k):
		arr = [i % k for i in range(n)]
		ans = [0] * n
		adj = {}
		for i in range(n):
			adj[i] = []
		for i in range(n // 2):
			adj[arr[i]].append(arr[n - i - 1])
			adj[arr[n - i - 1]].append(arr[i])
		self.dfs(0, ans, adj)
		res = ''
		for i in range(n):
			res += str(ans[arr[i]])
		return res