Dado un rectángulo amxn, ¿cuántos cuadrados hay en él?
Ejemplos:
Input: m = 2, n = 2 Output: 5 There are 4 squares of size 1x1 + 1 square of size 2x2. Input: m = 4, n = 3 Output: 20 There are 12 squares of size 1x1 + 6 squares of size 2x2 + 2 squares of size 3x3.
Resolvamos primero este problema para m = n, es decir, para un cuadrado:
Para m = n = 1, salida: 1
Para m = n = 2, salida: 4 + 1 [ 4 de tamaño 1×1 + 1 de tamaño 2×2 ]
Para m = n = 3, salida: 9 + 4 + 1 [ 9 de tamaño 1×1 + 4 de tamaño 2×2 + 1 de tamaño 3×3 ]
Para m = n = 4, salida 16 + 9 + 4 + 1 [ 16 de tamaño 1×1 + 9 de tamaño 2×2 + 4 de tamaño 3×3 + 1 de tamaño 4×4 ]
En general, parece ser n^2 + (n-1) ^2 + … 1 = n(n+1)(2n+1)/6
Resolvamos este problema cuando m puede no ser igual a n:
Supongamos que m <= n
De la explicación anterior, sabemos que el número de cuadrados en la array amxm es m(m+1)(2m+1)/6
¿Qué sucede cuando agregamos una columna, es decir, cuál es el número de cuadrados en la array mx (m+1)?
Cuando añadimos una columna, el número de cuadrados aumentado es m + (m-1) + … + 3 + 2 + 1
[ m cuadrados de tamaño 1×1 + (m-1) cuadrados de tamaño 2×2 + … + 1 cuadrado de tamaño mxm ]
Que es igual a m(m+1)/2
Entonces, cuando agregamos (nm) columnas, el número total de cuadrados aumentado es (nm)*m(m+1)/2.
Entonces, el número total de cuadrados es m(m+1)(2m+1)/6 + (nm)*m(m+1)/2.
Usando la misma lógica podemos probar cuando n <= m.
Entonces, en general,
Total number of squares = m x (m+1) x (2m+1)/6 + (n-m) x m x (m+1)/2 when n is larger dimension
Usando la lógica anterior para el rectángulo, también podemos probar que el número de cuadrados en un cuadrado es n(n+1)(2n+1)/6
A continuación se muestra la implementación de la fórmula anterior.
C++
// C++ program to count squares // in a rectangle of size m x n #include<iostream> using namespace std; // Returns count of all squares // in a rectangle of size m x n int countSquares(int m, int n) { // If n is smaller, swap m and n if (n < m) swap(m, n); // Now n is greater dimension, // apply formula return m * (m + 1) * (2 * m + 1) / 6 + (n - m) * m *(m + 1) / 2; } // Driver Code int main() { int m = 4, n = 3; cout << "Count of squares is " << countSquares(m, n); }
C
// C program to count squares // in a rectangle of size m x n #include <stdio.h> // Returns count of all squares // in a rectangle of size m x n int countSquares(int m, int n) { int temp; // If n is smaller, swap m and n if (n < m) { temp=n; n=m; m=temp; } // Now n is greater dimension, // apply formula return m * (m + 1) * (2 * m + 1) / 6 + (n - m) * m *(m + 1)/ 2; } // Driver Code int main() { int m = 4, n = 3; printf("Count of squares is %d",countSquares(m, n)); } // This code is contributed by Hemant Jain.
Java
// Java program to count squares // in a rectangle of size m x n class GFG { // Returns count of all squares // in a rectangle of size m x n static int countSquares(int m, int n) { // If n is smaller, swap m and n if (n < m) { // swap(m, n) int temp = m; m = n; n = temp; } // Now n is greater dimension, // apply formula return m * (m + 1) * (2 * m + 1) / 6 + (n - m) * m * (m + 1) / 2; } // Driver Code public static void main(String[] args) { int m = 4, n = 3; System.out.println("Count of squares is " + countSquares(m, n)); } }
Python3
# Python3 program to count squares # in a rectangle of size m x n # Returns count of all squares # in a rectangle of size m x n def countSquares(m, n): # If n is smaller, swap m and n if(n < m): temp = m m = n n = temp # Now n is greater dimension, # apply formula return ((m * (m + 1) * (2 * m + 1) / 6 + (n - m) * m * (m + 1) / 2)) # Driver Code if __name__=='__main__': m = 4 n = 3 print("Count of squares is " ,countSquares(m, n)) # This code is contributed by mits.
C#
// C# program to count squares in a rectangle // of size m x n using System; class GFG { // Returns count of all squares in a // rectangle of size m x n static int countSquares(int m, int n) { // If n is smaller, swap m and n if (n < m) { // swap(m,n) int temp = m; m = n; n = temp; } // Now n is greater dimension, apply // formula return m * (m + 1) * (2 * m + 1) / 6 + (n - m) * m * (m + 1) / 2; } // Driver method public static void Main() { int m = 4, n = 3; Console.WriteLine("Count of squares is " + countSquares(m, n)); } } //This code is contributed by vt_m.
PHP
<?php // PHP program to count squares // in a rectangle of size m x n // Returns count of all squares // in a rectangle of size m x n function countSquares($m, $n) { // If n is smaller, swap m and n if ($n < $m) list($m, $n) = array($n, $m); // Now n is greater dimension, // apply formula return $m * ($m + 1) * (2 * $m + 1) / 6 + ($n - $m) * $m * ($m + 1) / 2; } // Driver Code $m = 4; $n = 3; echo("Count of squares is " . countSquares($m, $n)); // This code is contributed by Ajit. ?>
Javascript
<script> // javascript program to count squares // in a rectangle of size m x n // Returns count of all squares // in a rectangle of size m x n function countSquares( m, n) { // If n is smaller, swap m and n if (n < m) [m, n] = [n, m]; // Now n is greater dimension, // apply formula return m * (m + 1) * (2 * m + 1) / 6 + (n - m) * m *(m + 1) / 2; } // Driver Code let m = 4; let n = 3; document.write("Count of squares is "+countSquares(n, m)); // This code is contributed by jana_sayantan. </script>
Producción :
Count of Squares is 20
Complejidad del tiempo: O(1)
Espacio Auxiliar: O(1)
Solución alternativa:
- Tomemos m = 2, n = 3;
- El número de cuadrados del lado 1 será 6 ya que habrá dos casos uno como cuadrados de 1 unidad de lado junto con la horizontal(2) y el segundo caso como cuadrados de 1 unidad de lado junto con la vertical(3). que nos dan 2*3 = 6 cuadrados.
- Cuando el lado es de 2 unidades, un caso será como cuadrados del lado de 2 unidades a lo largo de un solo lugar horizontalmente y el segundo caso como dos lugares verticalmente. Entonces, el número de cuadrados = 2
- Entonces podemos deducir que, Número de cuadrados de tamaño 1*1 será m*n. El número de cuadrados de tamaño 2*2 será (n-1)(m-1). De esta manera, el número de cuadrados de tamaño n será 1*(m-n+1).
La fórmula final para el número total de cuadrados será n*(n+1)(3m-n+1)/6 .
C++
// C++ program to count squares // in a rectangle of size m x n #include <iostream> using namespace std; // Returns count of all squares // in a rectangle of size m x n int countSquares(int m, int n) { // If n is smaller, swap m and n if (n < m) { int temp = m; m = n; n = temp; } // Now n is greater dimension, // apply formula return n * (n + 1) * (3 * m - n + 1) / 6; } // Driver Code int main() { int m = 4, n = 3; cout << "Count of squares is " << countSquares(m, n); } // This code is contributed by 29AjayKumar
C
// C program to count squares // in a rectangle of size m x n #include <stdio.h> // Returns count of all squares // in a rectangle of size m x n int countSquares(int m, int n) { // If n is smaller, swap m and n if (n < m) { int temp = m; m = n; n = temp; } // Now n is greater dimension, // apply formula return n * (n + 1) * (3 * m - n + 1) / 6; } // Driver Code int main() { int m = 4, n = 3; printf("Count of squares is %d",countSquares(m, n)); } // This code is contributed by Hemant Jain
Java
// Java program to count squares // in a rectangle of size m x n import java.util.*; class GFG { // Returns count of all squares // in a rectangle of size m x n static int countSquares(int m, int n) { // If n is smaller, swap m and n if (n < m) { int temp = m; m = n; n = temp; } // Now n is greater dimension, // apply formula return n * (n + 1) * (3 * m - n + 1) / 6; } // Driver Code public static void main(String[] args) { int m = 4; int n = 3; System.out.print("Count of squares is " + countSquares(m, n)); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to count squares # in a rectangle of size m x n # Returns count of all squares # in a rectangle of size m x n def countSquares(m, n): # If n is smaller, swap m and n if(n < m): temp = m m = n n = temp # Now n is greater dimension, # apply formula return n * (n + 1) * (3 * m - n + 1) // 6 # Driver Code if __name__=='__main__': m = 4 n = 3 print("Count of squares is", countSquares(m, n)) # This code is contributed by AnkitRai01
C#
// C# program to count squares // in a rectangle of size m x n using System; class GFG { // Returns count of all squares // in a rectangle of size m x n static int countSquares(int m, int n) { // If n is smaller, swap m and n if (n < m) { int temp = m; m = n; n = temp; } // Now n is greater dimension, // apply formula return n * (n + 1) * (3 * m - n + 1) / 6; } // Driver Code public static void Main(String[] args) { int m = 4; int n = 3; Console.Write("Count of squares is " + countSquares(m, n)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript program to count squares // in a rectangle of size m x n // Returns count of all squares // in a rectangle of size m x n function countSquares(m , n) { // If n is smaller, swap m and n if (n < m) { var temp = m; m = n; n = temp; } // Now n is greater dimension, // apply formula return n * (n + 1) * (3 * m - n + 1) / 6; } // Driver Code var m = 4; var n = 3; document.write("Count of squares is " + countSquares(m, n)); // This code is contributed by shikhasingrajput </script>
Producción :
Count of Squares is 20
Complejidad del tiempo: O(1)
Espacio Auxiliar: O(1)
Gracias a Pranav por proporcionar esta solución alternativa.
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