Comprobar si se puede obtener un área P de un área de N * M

Dados los números enteros N , M y P , la tarea es verificar si es posible encontrar un área rectangular de P unidades cuadradas dentro de un área rectangular de N × M unidades cuadradas.

Ejemplos:

Entrada: N = 3, M = 3, P = 4
Salida: SÍ
Explicación: Rectángulo de 2 x 2 unidades cuadradas de área

Entrada: N = 4, M = 4, P = 7
Salida: NO

Enfoque: siga los pasos a continuación para resolver el problema

• Encuentre todos los factores de p y guárdelos en el vector, digamos factores .
• Mantener orden N ≤ M .
• Atraviesa los factores del vector .
  • Para cada elemento de la array factores[i] , verifique si factores[i] ≤ N y p / factores[i] ≤ M , donde factores[i] y p / factores[i] representan las dimensiones del área rectangular.
  • Si se encuentra que es cierto, escriba SÍ y devuélvalo.
• De lo contrario, imprima NO

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a rectangle
// of p sq units can be formed from
//  an area of n * m sq units
void splitArea(int n, int m, int p)
{
    // Maintain order n <= m
    if (n > m)
        swap(n, m);
 
    vector<int> factors;
 
    // Iterate to find factors of p
    for (int i = 1; i * i <= p; i++) {
 
        // p is divisible by i
        if (p % i == 0) {
            factors.push_back(i);
        }
    }
 
    for (int i = 0; i < (int)factors.size();
         i++) {
 
        // Check if dimensions
        // lie in given area
        if (factors[i] <= n &&
            p / factors[i] <= m) {
 
            cout << "YES";
            return;
        }
    }
 
    cout << "NO";
}
 
// Driver Code
int main()
{
    int n = 3, m = 3, p = 4;
    splitArea(n, m, p);
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Function to swap two numbers
  // Using temporary variable
  static void swap(int m, int n)
  {
     
    // Swapping the values
    int temp = m;
    m = n;
    n = temp;
  }
 
  // Function to check if a rectangle
  // of p sq units can be formed from
  //  an area of n * m sq units
  static void splitArea(int n, int m, int p)
  {
 
    // Maintain order n <= m
    if (n > m)
      swap(n, m);
    ArrayList<Integer> factors = new ArrayList<Integer>();
 
    // Iterate to find factors of p
    for (int i = 1; i * i <= p; i++)
    {
 
      // p is divisible by i
      if (p % i == 0)
      {
        factors.add(i);
      }
    }
 
    for (int i = 0; i < (int)factors.size();
         i++)
    {
 
      // Check if dimensions
      // lie in given area
      if (factors.get(i) <= n &&
          p / factors.get(i) <= m)
      {
        System.out.print("YES");
        return;
      }
    }
 
    System.out.print("NO");
  }
 
 
// Driver code
public static void main(String[] args)
{
    int n = 3, m = 3, p = 4;
    splitArea(n, m, p);
}
}
 
// This code is contributed by code_hunt.

# Python3 program for the above approach
 
# Function to check if a rectangle
# of p sq units can be formed from
# an area of n * m sq units
def splitArea(n, m, p):
   
    # Maintain order n <= m
    if (n > m):
        n, m = m, n
    factors = []
 
    # Iterate to find factors of p
    for i in range(1, p + 1):
 
        # p is divisible by i
        if (p % i == 0):
            factors.append(i)
 
    for i in range(len(factors)):
       
        # Check if dimensions
        # lie in given area
        if (factors[i] <= n and p // factors[i] <= m):
            print("YES")
            return
 
    print("NO")
 
# Driver Code
if __name__ == '__main__':
    n, m, p = 3, 3, 4
    splitArea(n, m, p)
 
    # This code is contributed by mohit kumar 29.

// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
   
  // Function to swap two numbers
  // Using temporary variable
  static void swap(int m, int n)
  {
     
    // Swapping the values
    int temp = m;
    m = n;
    n = temp;
  }
 
  // Function to check if a rectangle
  // of p sq units can be formed from
  //  an area of n * m sq units
  static void splitArea(int n, int m, int p)
  {
 
    // Maintain order n <= m
    if (n > m)
      swap(n, m);
    List<int> factors = new List<int>();
 
    // Iterate to find factors of p
    for (int i = 1; i * i <= p; i++)
    {
 
      // p is divisible by i
      if (p % i == 0)
      {
        factors.Add(i);
      }
    }
 
    for (int i = 0; i < (int)factors.Count;
         i++)
    {
 
      // Check if dimensions
      // lie in given area
      if (factors[i] <= n &&
          p / factors[i] <= m)
      {
        Console.Write("YES");
        return;
      }
    }
 
    Console.Write("NO");
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int n = 3, m = 3, p = 4;
    splitArea(n, m, p);
  }
}
 
// This code is contributed by splevel62.

<script>
      // JavaScript program for the above approach
      // Function to swap two numbers
      // Using temporary variable
      function swap(m, n) {
        // Swapping the values
        var temp = m;
        m = n;
        n = temp;
      }
 
      // Function to check if a rectangle
      // of p sq units can be formed from
      // an area of n * m sq units
      function splitArea(n, m, p) {
        // Maintain order n <= m
        if (n > m) swap(n, m);
        var factors = new Array();
 
        // Iterate to find factors of p
        for (var i = 1; i * i <= p; i++) {
          // p is divisible by i
          if (p % i == 0) {
            factors.push(i);
          }
        }
 
        for (var i = 0; i < factors.length; i++) {
          // Check if dimensions
          // lie in given area
          if (factors[i] <= n && p / factors[i] <= m) {
            document.write("YES");
            return;
          }
        }
 
        document.write("NO");
      }
 
      // Driver code
      var n = 3,
        m = 3,
        p = 4;
      splitArea(n, m, p);
    </script>

YES

Complejidad de Tiempo: O(√P)
Espacio Auxiliar: O(log(P))