Given two integers n and m. Find the longest contiguous subset in binary representation of both the numbers and their decimal value.
Example 1:
Input : n = 10, m = 11 Output : 5 Explanation : Binary representation of 10 -> 1010 11 -> 1011 longest common substring in both is 101 and decimal value of 101 is 5
Example 2:
Input : n = 8, m = 16 Output : 8 Explanation : Binary representation of 8 -> 1000 16 -> 10000 longest common substring in both is 1000 and decimal value of 1000 is 8
Example 3:
Input : n = 0, m = 8 Output : 9 Explanation : Binary representation of 0 -> 0 8 -> 1000 longest common substring in both is 0 and decimal value of 0 is 0
Question Source:https://www.geeksforgeeks.org/citrix-interview-experience-set-5-campus/
Prerequisite :
We convert given numbers to their binary representations and store binary representations in two strings. Once we get strings, we find the longest common substring by trying all length substrings starting from maximum possible length.
Implementation:
C++
// CPP program to find longest contiguous// subset in binary representation of given// two numbers n and m#include <bits/stdc++.h>using namespace std;// utility function which returns// decimal value of binary representationint getDecimal(string s){ int len = s.length(); int ans = 0; int j = 0; for (int i = len - 1; i >= 0; i--) { if (s[i] == '1') ans += pow(2, j); j += 1; } return ans;}// Utility function which convert decimal// number to its binary representationstring convertToBinary(int n){ string temp; while (n > 0) { int rem = n % 2; temp.push_back(48 + rem); n = n / 2; } reverse(temp.begin(), temp.end()); return temp;}// utility function to check all the// substrings and get the longest substring.int longestCommon(int n, int m){ int mx = -INT_MAX; // maximum length string s1 = convertToBinary(n); string s2 = convertToBinary(m); string res; // final resultant string int len = s1.length(); int l = len; // for every substring of s1, // check if its length is greater than // previously found string // and also it is present in string s2 while (len > 0) { for (int i = 0; i < l - len + 1; i++) { string temp = s1.substr(i, len); int tlen = temp.length(); if (tlen > mx && s2.find(temp) != string::npos) { res = temp; mx = tlen; } } len = len - 1; } // If there is no common string if (res == "") return -1; return getDecimal(res);}// driver programint main(){ int n = 10, m = 11; cout << "longest common decimal value : " << longestCommon(m, n) << endl; return 0;} |
Java
// Java program to find longest contiguous// subset in binary representation of given// two numbers n and mpublic class GFG{ // utility function to check all the // substrings and get the longest substring. static int longestCommon(int n, int m) { int mx = -Integer.MAX_VALUE; // maximum length String s1 = Integer.toBinaryString(n); String s2 = Integer.toBinaryString(m); String res = null; // final resultant string int len = s1.length(); int l = len; // for every substring of s1, // check if its length is greater than // previously found string // and also it is present in string s2 while (len > 0) { for (int i = 0; i < l - len + 1; i++) { String temp = s1.substring(i, i + len); int tlen = temp.length(); if (tlen > mx && s2.contains(temp)) { res = temp; mx = tlen; } } len = len - 1; } // If there is no common string if(res == "") return -1; return Integer.parseInt(res,2); } // driver program to test above function public static void main(String[] args) { int n = 10; int m = 11; System.out.println("Longest common decimal value : " +longestCommon(m, n)); }}// This code is Contributed by Sumit Ghosh |
Python3
# Python3 program to find longest contiguous# subset in binary representation of given# two numbers n and m# utility function which returns# decimal value of binary representationdef getDecimal(s): lenn = len(s) ans = 0 j = 0 for i in range(lenn - 1, -1, -1): if (s[i] == '1'): ans += pow(2, j) j += 1 return ans# Utility function which convert decimal# number to its binary representationdef convertToBinary(n): return bin(n)[2:]# utility function to check all the# substrings and get the longest substring.def longestCommon(n, m): mx = -10**9 # maximum length s1 = convertToBinary(n) s2 = convertToBinary(m) #print(s1,s2) res="" # final resultant string lenn = len(s1) l = lenn # for every subof s1, # check if its length is greater than # previously found string # and also it is present in s2 while (lenn > 0): for i in range(l - lenn + 1): temp = s1[i:lenn + 1] # print(temp) tlenn = len(temp) if (tlenn > mx and( s2.find(temp) != -1)): res = temp mx = tlenn lenn = lenn - 1 # If there is no common string if (res == ""): return -1 return getDecimal(res)# Driver Coden = 10m = 11print("longest common decimal value : ", longestCommon(m, n))# This code is contributed by Mohit Kumar |
C#
// C# program to find longest contiguous // subset in binary representation of given // two numbers n and m using System;using System.Collections.Generic;class GFG { // utility function to check all the // substrings and get the longest substring. static int longestCommon(int n, int m) { int mx = -int.MaxValue; // maximum length String s1 = Convert.ToString(n, 2); String s2 = Convert.ToString(m, 2);; String res = null; // final resultant string int len = s1.Length; int l = len; // for every substring of s1, // check if its length is greater than // previously found string // and also it is present in string s2 while (len > 0) { for (int i = 0; i < l - len + 1; i++) { String temp = s1.Substring(i, len); int tlen = temp.Length; if (tlen > mx && s2.Contains(temp)) { res = temp; mx = tlen; } } len = len - 1; } // If there is no common string if(res == "") return -1; return Convert.ToInt32(res, 2); } // Driver code public static void Main(String[] args) { int n = 10; int m = 11; Console.WriteLine("Longest common decimal value : " +longestCommon(m, n)); } } // This code contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to find longest contiguous// subset in binary representation of given// two numbers n and m // utility function to check all the // substrings and get the longest substring. function longestCommon(n,m) { let mx = -Number.MAX_VALUE; // maximum length let s1 = (n >>> 0).toString(2); let s2 = (m >>> 0).toString(2); let res = null; // final resultant string let len = s1.length; let l = len; // for every substring of s1, // check if its length is greater than // previously found string // and also it is present in string s2 while (len > 0) { for (let i = 0; i < l - len + 1; i++) { let temp = s1.substring(i, i + len); let tlen = temp.length; if (tlen > mx && s2.includes(temp)) { res = temp; mx = tlen; } } len = len - 1; } // If there is no common string if(res == "") return -1; return parseInt(res, 2); } // driver program to test above function let n = 10; let m = 11; document.write("Longest common decimal value : " +longestCommon(m, n)); // This code is contributed by unknown2108</script> |
Output
longest common decimal value : 5
Optimizations to above approach:
The above solution can be optimized by methods discussed in below posts:
Dynamic Programming | Set 29 (Longest Common Substring)
This article is contributed by Mandeep Singh. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
