Dados dos enteros n y m. Encuentre el subconjunto contiguo más largo en representación binaria tanto de los números como de su valor decimal.
Ejemplo 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
Ejemplo 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
Ejemplo 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
Fuente de la pregunta: https://www.geeksforgeeks.org/citrix-interview-experience-set-5-campus/
Requisito previo :
- substr C++
- encontrar C++
Convertimos números dados a sus representaciones binarias y almacenamos representaciones binarias en dos strings. Una vez que obtenemos strings, encontramos la substring común más larga probando todas las substrings de longitud a partir de la longitud máxima posible.
Implementación:
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 representation
int 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 representation
string 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 program
int 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 m
public 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 representation
def 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 representation
def 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 Code
n = 10
m = 11
print("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>
Producción
longest common decimal value : 5
Optimizaciones para el enfoque anterior:
la solución anterior se puede optimizar mediante métodos discutidos en las publicaciones a continuación:
Programación dinámica | Conjunto 29 (Substring común más larga)
Este artículo es una contribución de Mandeep Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA