Dados dos números enteros N y K donde N denota el tamaño unitario de un Triángulo Equilátero más grande, la tarea es encontrar el número de un triángulo equilátero de tamaño K que están presentes en el triángulo más grande de lado N.
Ejemplos:
Entrada: N = 4, K = 3
Salida: 3
Explicación:
Hay 3 triángulos equiláteros de 3 unidades de tamaño que están presentes en el triángulo equilátero más grande de 4 unidades de tamaño.Entrada: N = 4, K = 2
Salida: 7
Explicación:
Hay 7 triángulos equiláteros de 2 unidades de tamaño que están presentes en el triángulo equilátero más grande de 4 unidades de tamaño.
Enfoque ingenuo: la idea es iterar sobre todos los tamaños posibles del triángulo equilátero más grande para verificar la cantidad de triángulos con el tamaño K requerido e imprimir el recuento total de triángulos.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, tenga en cuenta los siguientes puntos:
- El número de triángulos con un pico en la dirección ascendente del tamaño K presentes en el tamaño N es igual a ((N – K +1) * (N – K + 2))/2 .
- El número de triángulos invertidos con un pico en la dirección hacia abajo de tamaño K presentes en el tamaño N es igual a ((N – 2K + 1) * (N – 2K + 2))/2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to find the number of // equilateral triangle formed // within another triangle int No_of_Triangle(int N, int K) { // Check for the valid condition if (N < K) return -1; else { int Tri_up = 0; // Number of triangles having // upward peak Tri_up = ((N - K + 1) * (N - K + 2)) / 2; int Tri_down = 0; // Number of inverted triangles Tri_down = ((N - 2 * K + 1) * (N - 2 * K + 2)) / 2; // Total no. of K sized triangle return Tri_up + Tri_down; } } // Driver Code int main() { // Given N and K int N = 4, K = 2; // Function Call cout << No_of_Triangle(N, K); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the number of // equilateral triangle formed // within another triangle static int No_of_Triangle(int N, int K) { // Check for the valid condition if (N < K) return -1; else { int Tri_up = 0; // Number of triangles having // upward peak Tri_up = ((N - K + 1) * (N - K + 2)) / 2; int Tri_down = 0; // Number of inverted triangles Tri_down = ((N - 2 * K + 1) * (N - 2 * K + 2)) / 2; // Total no. of K sized triangle return Tri_up + Tri_down; } } // Driver Code public static void main(String[] args) { // Given N and K int N = 4, K = 2; // Function Call System.out.print(No_of_Triangle(N, K)); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 program for the above approach # Function to find the number of # equilateral triangle formed # within another triangle def No_of_Triangle(N, K): # Check for the valid condition if (N < K): return -1; else: Tri_up = 0; # Number of triangles having # upward peak Tri_up = ((N - K + 1) * (N - K + 2)) // 2; Tri_down = 0; # Number of inverted triangles Tri_down = ((N - 2 * K + 1) * (N - 2 * K + 2)) // 2; # Total no. of K sized triangle return Tri_up + Tri_down; # Driver Code if __name__ == '__main__': # Given N and K N = 4; K = 2; # Function Call print(No_of_Triangle(N, K)); # This code is contributed by sapnasingh4991
C#
// C# program for the above approach using System; class GFG{ // Function to find the number of // equilateral triangle formed // within another triangle static int No_of_Triangle(int N, int K) { // Check for the valid condition if (N < K) return -1; else { int Tri_up = 0; // Number of triangles having // upward peak Tri_up = ((N - K + 1) * (N - K + 2)) / 2; int Tri_down = 0; // Number of inverted triangles Tri_down = ((N - 2 * K + 1) * (N - 2 * K + 2)) / 2; // Total no. of K sized triangle return Tri_up + Tri_down; } } // Driver Code public static void Main(String[] args) { // Given N and K int N = 4, K = 2; // Function Call Console.Write(No_of_Triangle(N, K)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // JavaScript program for the above approach // Function to find the number of // equilateral triangle formed // within another triangle function No_of_Triangle(N, K) { // Check for the valid condition if (N < K) return -1; else { let Tri_up = 0; // Number of triangles having // upward peak Tri_up = Math.floor(((N - K + 1) * (N - K + 2)) / 2); let Tri_down = 0; // Number of inverted triangles Tri_down = Math.floor(((N - 2 * K + 1) * (N - 2 * K + 2)) / 2); // Total no. of K sized triangle return Tri_up + Tri_down; } } // Driver Code // Given N and K let N = 4, K = 2; // Function Call document.write(No_of_Triangle(N, K)); // This code is contributed by Surbhi Tyagi. </script>
7
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por thakurabhaysingh445 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA