Nos dan n bloques de tamaño 1 x 1, necesitamos encontrar el perímetro mínimo de la cuadrícula formada por estos bloques.
Ejemplos:
Input : n = 4 Output : 8 Minimum possible perimeter with 4 blocks is 8. See below explanation. Input : n = 11 Output : 14 The square grid of above examples would be as
Tomemos un ejemplo para ver un patrón. Digamos que tenemos 4 bloques, las siguientes son diferentes posibilidades
+--+--+--+--+ | | | | | Perimeter = 10 +--+--+--+--+ +--+--+--+ | | | | Perimeter = 10 +--+--+--+ | | +--+ +--+--+--+ | | | | Perimeter = 10 +--+--+--+ | | +--+ +--+--+ | | | Perimeter = 8 +--+--+ | | | +--+--+
Si hacemos algunos ejemplos con lápiz y papel, podemos notar que el perímetro se vuelve mínimo cuando la forma formada se acerca más a un cuadrado. La razón de esto es que queremos que los lados máximos de los bloques miren dentro de la forma para que el perímetro de la forma sea mínimo.
Si el número de bloques es un cuadrado perfecto, el perímetro sería simplemente 4*sqrt(n).
Pero, si el Número de bloques no es una raíz cuadrada perfecta, calculamos el número de filas y columnas más cercanas a la raíz cuadrada. Después de colocar los bloques en un rectángulo, todavía nos quedan bloques, entonces simplemente agregaremos 2 al perímetro porque solo quedarían 2 lados adicionales.
La implementación de la idea anterior se da a continuación.
C++
// CPP program to find minimum // perimeter using n blocks. #include <bits/stdc++.h> using namespace std; int minPerimeter(int n) { int l = sqrt(n); int sq = l * l; // if n is a perfect square if (sq == n) return l * 4; else { // Number of rows long long int row = n / l; // perimeter of the // rectangular grid long long int perimeter = 2 * (l + row); // if there are blocks left if (n % l != 0) perimeter += 2; return perimeter; } } // Driver code int main() { int n = 10; cout << minPerimeter(n); return 0; }
Java
// JAVA Code to find minimum // perimeter using n blocks import java.util.*; class GFG { public static long minPerimeter(int n) { int l = (int) Math.sqrt(n); int sq = l * l; // if n is a perfect square if (sq == n) return l * 4; else { // Number of rows long row = n / l; // perimeter of the // rectangular grid long perimeter = 2 * (l + row); // if there are blocks left if (n % l != 0) perimeter += 2; return perimeter; } } // Driver code public static void main(String[] args) { int n = 10; System.out.println(minPerimeter(n)); } } // This code is contributed by Arnav Kr. Mandal
Python3
# Python3 program to find minimum # perimeter using n blocks. import math def minPerimeter(n): l = math.sqrt(n) sq = l * l # if n is a perfect square if (sq == n): return l * 4 else : # Number of rows row = n / l # perimeter of the # rectangular grid perimeter = 2 * (l + row) # if there are blocks left if (n % l != 0): perimeter += 2 return perimeter # Driver code n = 10 print(int(minPerimeter(n))) # This code is contributed by # Prasad Kshirsagar
C#
// C# Code to find minimum // perimeter using n blocks using System; class GFG { public static long minPerimeter(int n) { int l = (int) Math.Sqrt(n); int sq = l * l; // if n is a perfect square if (sq == n) return l * 4; else { // Number of rows long row = n / l; // perimeter of the // rectangular grid long perimeter = 2 * (l + row); // if there are blocks left if (n % l != 0) perimeter += 2; return perimeter; } } // Driver code public static void Main() { int n = 10; Console.Write(minPerimeter(n)); } } // This code is contributed by nitin mittal
PHP
<?php // PHP program to find minimum // perimeter using n blocks. function minPerimeter($n) { $l = floor(sqrt($n)); $sq = $l * $l; // if n is a perfect square if ($sq == $n) return $l * 4; else { // Number of rows $row = floor($n / $l); // perimeter of the // rectangular grid $perimeter = 2 * ($l + $row); // if there are blocks left if ($n % $l != 0) $perimeter += 2; return $perimeter; } } // Driver code $n = 10; echo minPerimeter($n); // This code is contributed // by nitin mittal. ?>
Javascript
<script> // JavaScript program for the // above approach function minPerimeter(n) { let l = Math.sqrt(n); let sq = l * l; // if n is a perfect square if (sq == n) return l * 4; else { // Number of rows let row = n / l; // perimeter of the // rectangular grid let perimeter = 2 * (l + row); // if there are blocks left if (n % l != 0) perimeter += 2; return perimeter; } } // Driver Code let n = 10; document.write(Math.floor(minPerimeter(n))) </script>
Producción :
14
Complejidad de tiempo : O(logn)
Espacio auxiliar : O(1)
Referencias:
http://mathforum.org/library/drmath/view/61595.html
intermath.coe.uga.edu/tweb/gcsu-geo-spr06/aheath/aheath_rectperimeter.doc
Este artículo es una contribución de Sarthak Kohli . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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