Given a number N, the task is to determine if it is possible to make Pascal’s triangle with a complete layer by using total number N integer if possible print Yes otherwise print No.
Note: Pascal’s triangle is a triangular array of the binomial coefficients. Following are the first 6 rows of Pascal’s Triangle.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
In Pascal’s Triangle from the topmost layer there is 1 integer, at every next layer from top to bottom size of the layer increased by 1.
Examples:
Input: N = 10
Output: Yes
Explanation:
You can use 1, 2, 3 and 4 integers to make first, second, third, and fourth layer of pascal’s triangle respectively and also N = 10 satisfy by using (1 + 2 + 3 + 4) integers on each layer = 10.
Input: N = 5
Output: No
Explanation:
You can use 1 and 2 integers to make first and second layer respectively and after that you have only 2 integers left and you can’t make 3rd layer complete as that layer required 3 integers.
Approach: Here we are using integer 1, 2, 3, … on every layer starting from first layer, so we can only make Pascal’s triangle complete if it’s possible to represent N by the sum of 1 + 2 +…
- The sum of first X integers is given by
- We can only make pascal’s triangle by using N integers if and only if
where X must be a positive integer. So we have to check is there any positive integer value of x exist or not. - To determine value of X from second step we can deduced the formula as:
where X must be a positive integer. So we have to check is there any positive integer value of x exist or not.
- If the value of X integer for the given value of N then we can make Pascal Triangle. Otherwise, we can’t make Pascal Triangle.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if Pascaltriangle// can be made by N integersvoid checkPascaltriangle(int N){ // Find X double x = (sqrt(8 * N + 1) - 1) / 2; // If x is integer if (ceil(x) - x == 0) cout << "Yes"; else cout << "No";}// Driver Codeint main(){ // Given number N int N = 10; // Function Call checkPascaltriangle(N); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to check if Pascaltriangle// can be made by N integersstatic void checkPascaltriangle(int N){ // Find X double x = (Math.sqrt(8 * N + 1) - 1) / 2; // If x is integer if (Math.ceil(x) - x == 0) System.out.print("Yes"); else System.out.print("No");}// Driver Codepublic static void main(String[] args){ // Given number N int N = 10; // Function call checkPascaltriangle(N);}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program for the above approachimport math # Function to check if Pascaltriangle# can be made by N integersdef checkPascaltriangle(N): # Find X x = (math.sqrt(8 * N + 1) - 1) / 2 # If x is integer if (math.ceil(x) - x == 0): print("Yes") else: print("No")# Driver Code# Given number NN = 10# Function callcheckPascaltriangle(N)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{// Function to check if Pascaltriangle// can be made by N integersstatic void checkPascaltriangle(int N){ // Find X double x = (Math.Sqrt(8 * N + 1) - 1) / 2; // If x is integer if (Math.Ceiling(x) - x == 0) Console.Write("Yes"); else Console.Write("No");}// Driver Codepublic static void Main(String[] args){ // Given number N int N = 10; // Function call checkPascaltriangle(N);}}// This code is contributed by amal kumar choubey |
Javascript
<script> // JavaScript program for the above approach // Function to check if Pascaltriangle // can be made by N integers function checkPascaltriangle(N) { // Find X var x = (Math.sqrt(8 * N + 1) - 1) / 2; // If x is integer if (Math.ceil(x) - x == 0) document.write("Yes"); else document.write("No"); } // Driver Code // Given number N var N = 10; // Function Call checkPascaltriangle(N); </script> |
Yes
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
