Dada la altura H y el ancho W de un rectángulo, la tarea es encontrar el lado de un cuadrado del área mínima en la que dos rectángulos encajan completamente.
Nota:
- Dos rectángulos pueden tocarse por los lados o por las esquinas.
- Los rectángulos no pueden intersecarse entre sí.
- Los rectángulos también pueden tocar los lados del cuadrado, pero deben estar completamente dentro de él.
- Los rectángulos también se pueden girar.
Ejemplo :
Entrada: H = 4, W = 2
Salida: 4
Explicación:
El lado mínimo del cuadrado es 4
Entrada: H = 4, W = 4
Salida: 8
Enfoque:
Hay tres casos posibles:
- Al principio, verifique que la altura y el ancho dados sean iguales o no, si son iguales, entonces los rectángulos son en sí mismos un cuadrado, así que simplemente adjunte dos cuadrados y duplique el lado,
- Luego, si el primer caso no se cumple, verifique si la altura> el ancho o no,
si es mayor, luego duplique el valor del ancho y agréguelo al ancho y cree un nuevo ancho,
new_Width = ancho + ancho
-
- Luego encuentre la diferencia de ‘new_Width’ y ‘height’ y almacene la diferencia en una nueva variable «diff» ,
- Si ‘new_Width’ es menor que ‘height’ , agregue el valor «diff» a ‘new_Width’ , luego ‘height’ y ‘new_width’ son iguales y devuelven ‘new_Width’ , que es el lado del cuadrado mínimo .
- Si ‘new_Width’ es mayor que ‘height’ , agregue el valor «diff» a ‘height’ , luego ‘height’ y ‘width’ son iguales, y devuelve ‘height’ , que es el lado del mínimo cuadrado.
- Luego, si el segundo caso no está satisfecho, verifique si la altura <ancho ,
si es más pequeño, luego duplique el valor de ‘altura’ y agréguelo a la altura y cree una nueva altura,
new_Height = altura + altura
-
- Luego encuentre la diferencia de ‘new_Height’ y ‘width’ y almacene la diferencia en una nueva variable «diff» ,
- Si ‘new_Height’ es menor que ‘width’ , agregue el valor «diff» a ‘new_Height’ , luego ‘width’ y ‘new_Height’ son iguales y devuelven ‘new_Height’ , que es el lado del cuadrado mínimo .
- Si ‘new_Height’ es mayor que ‘width’ , agregue el valor «diff» a ‘width’ , luego ‘height’ y ‘width’ son iguales, y devuelva ‘height’ , que es el lado del mínimo cuadrado.
- Final
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
int minimalSquareSide(int a, int b)
{
// if 'a' and 'b' same
// then double 'a' or 'b'
// and return (2*a) or (2*b)
if (a == b) {
return 2 * a;
}
// check if a!=b
if (a != b) {
// if a > b
if (a > b) {
// double the smaller value
// that is 'b' and store
// it to 'newB'
int newB = b + b;
// find the difference of
// 'newB and 'a'
int diff = abs(newB - a);
// if 'newB' < a
if (newB < a) {
// then add the difference of
// 'newB' and 'a' to the 'b'
// to make 'b' and 'a' as same
b = newB + diff;
// return side of the
// square a or b
if (a == b)
return a;
return 0;
}
else {
// if 'newB' > a then
// then add the difference
// of 'newB' and 'a' to
// the 'a' to make 'a' and
// 'newB' as same
a = a + diff;
// return side of the
// square a or newB
if (a == newB)
return a;
return 0;
}
}
// if a < b
else {
// double the smaller value
// that is 'a' and store
// it to 'newA'
int newA = a + a;
// find the difference of
// 'newA and 'b'
int diff = abs(newA - b);
// if 'newA' < b
if (newA < b) {
// then add the difference
// of 'newA' and 'b' to
// the 'a' to make 'a'
// and 'b' as same
a = diff + newA;
// return side of the
// square a or b
if (a == b)
return a;
return 0;
}
else {
// if 'newA' > b then
// then add the difference
// of 'newA' and 'b' to
// the 'b' to make 'b' and
// 'newA' as same
b = b + diff;
// return side of the
// square b or newA
if (b == newA)
return b;
return 0;
}
}
}
}
// Drive Code
int main()
{
int H, W;
// Size of rectangle
H = 3, W = 1;
cout << minimalSquareSide(H, W) << endl;
return 0;
}
Java
// Java program of the above approach
class GFG{
public static int minimalSquareSide(int a, int b)
{
// If 'a' and 'b' same
// then double 'a' or 'b'
// and return (2*a) or (2*b)
if (a == b)
{
return 2 * a;
}
// Check if a!=b
if (a != b)
{
// If a > b
if (a > b)
{
// Double the smaller value
// that is 'b' and store
// it to 'newB'
int newB = b + b;
// Find the difference of
// 'newB and 'a'
int diff = Math.abs(newB - a);
// If 'newB' < a
if (newB < a)
{
// Then add the difference of
// 'newB' and 'a' to the 'b'
// to make 'b' and 'a' as same
b = newB + diff;
// Return side of the
// square a or b
if (a == b)
return a;
return 0;
}
else
{
// If 'newB' > a then
// then add the difference
// of 'newB' and 'a' to
// the 'a' to make 'a' and
// 'newB' as same
a = a + diff;
// Return side of the
// square a or newB
if (a == newB)
return a;
return 0;
}
}
// If a < b
else
{
// Double the smaller value
// that is 'a' and store
// it to 'newA'
int newA = a + a;
// Find the difference of
// 'newA and 'b'
int diff = Math.abs(newA - b);
// If 'newA' < b
if (newA < b)
{
// Then add the difference
// of 'newA' and 'b' to
// the 'a' to make 'a'
// and 'b' as same
a = diff + newA;
// Return side of the
// square a or b
if (a == b)
return a;
return 0;
}
else
{
// If 'newA' > b then
// then add the difference
// of 'newA' and 'b' to
// the 'b' to make 'b' and
// 'newA' as same
b = b + diff;
// Return side of the
// square b or newA
if (b == newA)
return b;
return 0;
}
}
}
return 0;
}
// Driver code
public static void main(String[] args)
{
int H, W;
// Size of rectangle
H = 3; W = 1;
System.out.println(minimalSquareSide(H, W));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach def minimalSquareSide(a, b): # If 'a' and 'b' same # then double 'a' or 'b' # and return (2*a) or (2*b) if (a == b): return 2 * a # Check if a!=b if (a != b): # If a > b if (a > b): # Double the smaller value # that is 'b' and store # it to 'newB' newB = b + b # Find the difference of # 'newB and 'a' diff = abs(newB - a) # If 'newB' < a if (newB < a): # Then add the difference of # 'newB' and 'a' to the 'b' # to make 'b' and 'a' as same b = newB + diff # Return side of the # square a or b if (a == b): return a return 0 else: # If 'newB' > a then # then add the difference # of 'newB' and 'a' to # the 'a' to make 'a' and # 'newB' as same a = a + diff # Return side of the # square a or newB if (a == newB): return a return 0 # If a < b else: # Double the smaller value # that is 'a' and store # it to 'newA' newA = a + a # Find the difference of # 'newA and 'b' diff = abs(newA - b) # If 'newA' < b if (newA < b): # Then add the difference # of 'newA' and 'b' to # the 'a' to make 'a' # and 'b' as same a = diff + newA # Return side of the # square a or b if (a == b): return a return 0 else: # If 'newA' > b then # then add the difference # of 'newA' and 'b' to # the 'b' to make 'b' and # 'newA' as same b = b + diff # Return side of the # square b or newA if (b == newA): return b return 0 # Driver code # Size of rectangle H = 3 W = 1 print(minimalSquareSide(H, W)) # This code is contributed by sanjoy_62
C#
// C# program of the above approach
using System;
class GFG{
public static int minimalSquareSide(int a, int b)
{
// If 'a' and 'b' same
// then double 'a' or 'b'
// and return (2*a) or (2*b)
if (a == b)
{
return 2 * a;
}
// Check if a!=b
if (a != b)
{
// If a > b
if (a > b)
{
// Double the smaller value
// that is 'b' and store
// it to 'newB'
int newB = b + b;
// Find the difference of
// 'newB and 'a'
int diff = Math.Abs(newB - a);
// If 'newB' < a
if (newB < a)
{
// Then add the difference of
// 'newB' and 'a' to the 'b'
// to make 'b' and 'a' as same
b = newB + diff;
// Return side of the
// square a or b
if (a == b)
return a;
return 0;
}
else
{
// If 'newB' > a then
// then add the difference
// of 'newB' and 'a' to
// the 'a' to make 'a' and
// 'newB' as same
a = a + diff;
// Return side of the
// square a or newB
if (a == newB)
return a;
return 0;
}
}
// If a < b
else
{
// Double the smaller value
// that is 'a' and store
// it to 'newA'
int newA = a + a;
// Find the difference of
// 'newA and 'b'
int diff = Math.Abs(newA - b);
// If 'newA' < b
if (newA < b)
{
// Then add the difference
// of 'newA' and 'b' to
// the 'a' to make 'a'
// and 'b' as same
a = diff + newA;
// Return side of the
// square a or b
if (a == b)
return a;
return 0;
}
else
{
// If 'newA' > b then
// then add the difference
// of 'newA' and 'b' to
// the 'b' to make 'b' and
// 'newA' as same
b = b + diff;
// Return side of the
// square b or newA
if (b == newA)
return b;
return 0;
}
}
}
return 0;
}
// Driver code
public static void Main(String[] args)
{
int H, W;
// Size of rectangle
H = 3; W = 1;
Console.WriteLine(minimalSquareSide(H, W));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// javascript program of the above approach
function minimalSquareSide(a , b)
{
// If 'a' and 'b' same
// then var 'a' or 'b'
// and return (2*a) or (2*b)
if (a == b)
{
return 2 * a;
}
// Check if a!=b
if (a != b)
{
// If a > b
if (a > b)
{
// Double the smaller value
// that is 'b' and store
// it to 'newB'
var newB = b + b;
// Find the difference of
// 'newB and 'a'
var diff = Math.abs(newB - a);
// If 'newB' < a
if (newB < a)
{
// Then add the difference of
// 'newB' and 'a' to the 'b'
// to make 'b' and 'a' as same
b = newB + diff;
// Return side of the
// square a or b
if (a == b)
return a;
return 0;
}
else
{
// If 'newB' > a then
// then add the difference
// of 'newB' and 'a' to
// the 'a' to make 'a' and
// 'newB' as same
a = a + diff;
// Return side of the
// square a or newB
if (a == newB)
return a;
return 0;
}
}
// If a < b
else
{
// Double the smaller value
// that is 'a' and store
// it to 'newA'
var newA = a + a;
// Find the difference of
// 'newA and 'b'
var diff = Math.abs(newA - b);
// If 'newA' < b
if (newA < b)
{
// Then add the difference
// of 'newA' and 'b' to
// the 'a' to make 'a'
// and 'b' as same
a = diff + newA;
// Return side of the
// square a or b
if (a == b)
return a;
return 0;
}
else
{
// If 'newA' > b then
// then add the difference
// of 'newA' and 'b' to
// the 'b' to make 'b' and
// 'newA' as same
b = b + diff;
// Return side of the
// square b or newA
if (b == newA)
return b;
return 0;
}
}
}
return 0;
}
// Driver code
var H, W;
// Size of rectangle
H = 3; W = 1;
document.write(minimalSquareSide(H, W));
// This code is contributed by 29AjayKumar
</script>
Producción:
3
Complejidad temporal: O(1)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por SoumikMondal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA