Given two integers N and M. Find the longest common contiguous subset in binary representation of both the numbers and print its decimal value.
Example 1:
Input: N = 10, M = 11
Output: 5
Explanation: 10 in Binary is "1010" and
11 in Binary is "1011". The longest common
contiguous subset is "101" which has a
decimal value of 5.
Ã¢â¬â¹Example 2:
Input: N = 8, M = 16
Output: 8
Explanation: 8 in Binary is "1000" and
16 in Binary is "10000". The longest common
contiguous subset is "1000" which has a
decimal value of 8.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestCommon() which takes two integers N and M as inputs and returns the Decimal representation of the longest common contiguous subset in the Binary representation of N and M.
Note: If there's a tie in the length of the longest common contiguous subset, return the one with the highest decimal value among them.
Expected Time Complexity: O((log(max (N, M))^{3}).
Expected Auxiliary Space: O((log(max (N, M))^{2}).
Constraints:
1<=N,M<=10^{18}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:

    def longestCommon(self, N, M):
        # code here

Solutions:
class Solution:

	def longestCommon(self, N, M):
		d = []
		e = []
		while N > 0:
			d.append(N % 2)
			N //= 2
		while M > 0:
			e.append(M % 2)
			M //= 2
		a1 = {}
		for i in range(len(d)):
			c = 0
			p = 1
			s = ''
			for j in range(i, len(d)):
				s += str(d[j])
				a1[s] = 1
		res = 0
		c2 = 0
		for i in range(len(e)):
			c = 0
			p = 1
			s = ''
			c1 = 0
			for j in range(i, len(e)):
				c += p * e[j]
				p *= 2
				s += str(e[j])
				c1 += 1
				if s in a1:
					if c1 > c2:
						res = c
						c2 = c1
					elif c1 == c2:
						res = max(res, c)
		return res


import numpy as np

class Solution:

	def longestCommon(self, n, m):
		x = bin(n)[2:]
		y = bin(m)[2:]
		l = []
		n = len(x)
		m = len(y)
		t = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if x[i - 1] == y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = 0
		mx = np.amax(t)
		for i in range(n + 1):
			for j in range(m + 1):
				if t[i][j] == mx:
					l.append([i, j])
		w = 0
		for i in l:
			(r, c) = (i[0], i[1])
			ans = ''
			while t[r][c] != 0:
				ans += y[c - 1]
				r -= 1
				c -= 1
			ans = ans[::-1]
			w = max(w, int(ans, 2))
		return w


class Solution:

	def longestCommon(self, N, M):
		n = bin(N)[2:]
		m = bin(M)[2:]
		dp = [[None] * (len(n) + 1) for i in range(len(m) + 1)]
		a = []
		ans = 0
		for i in range(len(m) + 1):
			for j in range(len(n) + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif m[i - 1] == n[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if dp[i][j] > ans:
						ans = dp[i][j]
						a = [(i, j)]
					elif dp[i][j] == ans:
						a.append((i, j))
				else:
					dp[i][j] = 0
		res = 0
		for (i, j) in a:
			s = ''
			while dp[i][j] != 0:
				s = m[i - 1] + s
				i -= 1
				j -= 1
			res = max(res, int(s, 2))
		return res


from itertools import combinations

class Solution:

	def longestCommon(self, N, M):
		a = bin(N)[2:]
		b = bin(M)[2:]
		x = [i for i in range(len(a) + 1)]
		y = [i for i in range(len(b) + 1)]
		ad = {}
		for (i, j) in combinations(x, 2):
			aad = a[i:j]
			if aad not in ad:
				ad[aad] = 1
		bd = []
		for (i, j) in combinations(y, 2):
			bbd = b[i:j]
			bd.append(bbd)
		ans = []
		for i in bd:
			if i in ad:
				ans.append(i)
		l = 0
		for i in ans:
			ll = len(i)
			if ll > l:
				l = ll
		z = []
		for i in ans:
			if len(i) == l:
				z.append(i)
		xyz = []
		for i in z:
			xyz.append(int(i, 2))
		return max(xyz)


class Solution:

	def longestCommon(self, N, M):
		a = bin(N)[2:]
		b = bin(M)[2:]
		n = len(a)
		m = len(b)
		dp = [[0] * (m + 1) for i in range(n + 1)]
		p = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if a[i - 1] == b[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					if p < dp[i][j]:
						p = dp[i][j]
						x = [(i, j)]
					elif p == dp[i][j]:
						x.append((i, j))
		s = 0
		for (i, j) in x:
			d = ''
			while dp[i][j] != 0:
				d = a[i - 1] + d
				i -= 1
				j -= 1
			s = max(s, int(d, base=2))
		return s
		return s


class Solution:

	def longestCommon(self, N, M):
		s1 = bin(N)[2:]
		s2 = bin(M)[2:]
		ans = 0
		(n, m) = (len(s1), len(s2))
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = 0
				ans = max(ans, dp[i][j])
		l = []
		for i in range(n + 1):
			for j in range(m + 1):
				if dp[i][j] == ans:
					l.append(i - 1)
		res = 0
		for i in range(len(l)):
			s = ''
			index = l[i]
			s = s1[index - ans + 1:index + 1]
			res = max(res, int(s, 2))
		return res


class Solution:

	def longestCommon(self, N, M):
		a = bin(N)[2:]
		b = bin(M)[2:]
		n = len(a)
		m = len(b)
		dp = []
		for i in range(n + 1):
			d = [0] * (m + 1)
			dp.append(d)
		sample = 0
		lj = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if a[i - 1] == b[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					ll = len(b[j - dp[i][j]:j])
					if ll > lj:
						sample = int(b[j - dp[i][j]:j], 2)
						lj = ll
					elif ll == lj:
						sample = max(sample, int(b[j - dp[i][j]:j], 2))
						lj = ll
				else:
					dp[i][j] = 0
		return sample