Perímetro mínimo de n bloques

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.
 

// 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 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 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# 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 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.
?>

<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.