Número de rectángulos únicos formados usando N cuadrados unitarios

Te dan N cuadrados unitarios (cuadrados con una longitud de lado de 1 unidad) y te piden que hagas rectángulos usando estos cuadrados. Tienes que contar el número de rectángulos rotacionalmente únicos que puedes hacer. ¿Qué significa rotacionalmente único? Bueno, dos rectángulos son rotacionalmente únicos si uno no se puede rotar para volverse equivalente al otro. 

Ejemplo: el rectángulo de 4 × 2 se puede girar 90 grados en el sentido de las agujas del reloj para que sea exactamente igual que el rectángulo de 2 × 4 y, por lo tanto, estos no son rotativamente únicos. 
 

Ejemplos: 

Input : N = 4
Output : 5
We can make following five rectangles 
1 x 1, 1 x 2, 2 x 2, 1 x 3 and 1 x 4

Input : N = 5
Output : 6

Input : 6
Output : 8

Entonces, ¿cómo resolvemos este problema? 
Cada rectángulo está determinado únicamente por su longitud y su altura. 
Un rectángulo de longitud = l y altura = h entonces l * h <= n se considera equivalente a un rectángulo de longitud = h y altura = l siempre que l no sea igual a h. Si podemos tener algún tipo de «ordenamiento» en estos pares, podemos evitar contar (l, h) y (h, l) como rectángulos diferentes. Una forma de definir tal orden es: 

Suponga que longitud <= altura y cuente para todos los pares tales que longitud*altura <= n. 
Tenemos, longitud <= altura 
o, longitud*longitud <= longitud*altura 
o, longitud*longitud <= n 
o, longitud <= sqrt(n) 

// C++ program to count rotationally equivalent
// rectangles with n unit squares
#include<bits/stdc++.h>
using namespace std;
 
int countRect(int n)
{
    int ans = 0;
    for (int length = 1; length <= sqrt(n); ++length)
    for (int height = length; height*length <= n; ++height)
            // height >= length is maintained
        ans++;
    return ans;
}
 
// Driver code
int main() {
    int n = 5;
    printf("%d", countRect(n));
    return 0;
}

// Java program to count rotationally equivalent
// rectangles with n unit squares
class GFG {
     
    static int countRect(int n)
    {
        int ans = 0;
         
        for (int length = 1; length <= Math.sqrt(n);
                                           ++length)
            for (int height = length; height*length <= n;
                                                ++height)
                // height >= length is maintained
                ans++;
             
        return ans;
    }
     
    //driver code
    public static void main (String[] args)
    {
        int n = 5;
         
        System.out.print(countRect(n));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to count rotationally
# equivalent rectangles with n unit squares
import math
 
def countRect(n):
 
    ans = 0
    for length in range(1, int(math.sqrt(n)) + 1):
        height = length
        while(height * length <= n):
             
            # height >= length is maintained
            ans += 1
            height += 1
    return ans
 
# Driver code
n = 5
print(countRect(n))
 
# This code is contributed by Anant Agarwal.

// C# program to count rotationally
// equivalent rectangles with n unit
// squares
using System;
 
class GFG {
     
    static int countRect(int n)
    {
        int ans = 0;
        for (int length = 1;
            length <= Math.Sqrt(n); ++length)
             
            for (int height = length;
                     height*length <= n; ++height)
                ans++;
                 
        return ans;
    }
     
    //driver code
    public static void Main()
    {
         
        int n = 5;
         
        Console.Write(countRect(n));
    }
}
 
//This code is contributed by Anant Agarwal.

<?php
// PHP program to count
// rotationally equivalent
// rectangles with n unit squares
function countRect($n)
{
    $ans = 0;
    for ($length = 1;
         $length <= sqrt($n); $length++)
    for ($height = $length;
         $height * $length <= $n; $height++)
            // height >= length is maintained
        $ans++;
    return $ans;
}
 
// Driver code
$n = 5;
echo countRect($n);
 
// This code is contributed by @ajit
?>

<script>
 
// Javascript program to count rotationally
// equivalent rectangles with n unit
// squares
function countRect(n)
{
    let ans = 0;
    for(let length = 1;
            length <= parseInt(Math.sqrt(n), 10);
          ++length)
           
        for(let height = length;
                height * length <= n;
              ++height)
            ans++;
               
    return ans;
}
 
// Driver code
let n = 5;
       
document.write(countRect(n));
 
// This code is contributed by divyesh072019
 
</script>

Producción : 

6 

Complejidad temporal: O(n√n) 
Espacio auxiliar: O(1)

Este artículo es una contribución de Aarti_Rathi y Hemang Sarkar . 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.