Given an integer N, the task is to find out whether it can be written as a sum of 2 triangular numbers (which may or may not be distinct).
Examples:
Input: N = 24
Output: YES
24 can be represented as 3+21.Input: N = 15
Output: NO
Approach: Consider all triangular numbers less than N i.e. sqrt(N) numbers. Let’s add them to a set, and for each triangular number X we check if N-X is present in the set. If it is true with any triangular number, then the answer is YES, otherwise the answer is NO.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible or notbool checkTriangularSumRepresentation(int n){ unordered_set<int> tri; int i = 1; // Store all triangular numbers up to N in a Set while (1) { int x = i * (i + 1) / 2; if (x >= n) break; tri.insert(x); i++; } // Check if a pair exists for (auto tm : tri) if (tri.find(n - tm) != tri.end()) return true; return false;}// Driver Codeint main(){ int n = 24; checkTriangularSumRepresentation(n) ? cout << "Yes" : cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function to check if it is possible or not static boolean checkTriangularSumRepresentation(int n) { HashSet<Integer> tri = new HashSet<>(); int i = 1; // Store all triangular numbers up to N in a Set while (true) { int x = i * (i + 1) / 2; if (x >= n) { break; } tri.add(x); i++; } // Check if a pair exists for (Integer tm : tri) { if (tri.contains(n - tm) && (n - tm) != (int) tri.toArray()[tri.size() - 1]) { return true; } } return false; } // Driver code public static void main(String[] args) { int n = 24; if (checkTriangularSumRepresentation(n)) { System.out.println("Yes"); } else { System.out.println("No"); } }}// This code has been contributed by 29AjayKumar |
Python 3
# Python3 implementation of the above approach # Function to check if it is possible or not def checkTriangularSumRepresentation(n) : tri = list(); i = 1; # Store all triangular numbers # up to N in a Set while (1) : x = i * (i + 1) // 2; if (x >= n) : break; tri.append(x); i += 1; # Check if a pair exists for tm in tri : if n - tm in tri: return True; return False; # Driver Code if __name__ == "__main__" : n = 24; if checkTriangularSumRepresentation(n) : print("Yes") else : print("No")# This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG { // Function to check if it is possible or not static bool checkTriangularSumRepresentation(int n) { HashSet<int> tri = new HashSet<int>(); int i = 1; // Store all triangular numbers up to N in a Set while (true) { int x = i * (i + 1) / 2; if (x >= n) { break; } tri.Add(x); i++; } // Check if a pair exists foreach (int tm in tri) { if (tri.Contains(n - tm)) { return true; } } return false; } // Driver code public static void Main(String[] args) { int n = 24; if (checkTriangularSumRepresentation(n)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}// This code contributed by Rajput-Ji |
PHP
<?php// PHP implementation of the above approach // Function to check if it is possible or not function checkTriangularSumRepresentation($n) { $tri = array(); $i = 1; // Store all triangular numbers // up to N in a Set while (true) { $x = $i * ($i + 1); if ($x >= $n) break; array_push($tri, $x); $i += 1; } // Check if a pair exists foreach($tri as $tm) if (in_array($n - $tm, $tri)) return true; return false; }// Driver Code $n = 24; if (checkTriangularSumRepresentation($n)) print("Yes");else print("No");// This code is contributed by mits?> |
Javascript
<script>// Javascript implementation of the above approach// Function to check if it is possible or notfunction checkTriangularSumRepresentation(n){ var tri = new Set(); var i = 1; // Store all triangular numbers up to N in a Set while (1) { var x = i * parseInt((i + 1) / 2); if (x >= n) break; tri.add(x); i++; } var ans = false; // Check if a pair exists tri.forEach(tm => { if (tri.has(n - tm)) ans = true }); return ans;}// Driver Codevar n = 24;checkTriangularSumRepresentation(n) ? document.write( "Yes") : document.write( "No");// This code is contributed by famously.</script> |
Output
Yes
Complexity Analysis:
- Time Complexity: O(Sqrt(N))
- Auxiliary Space: O(sqrt(N))
Second approach: Its very clear that N is positive because triangular numbers are numbers that are representable as k*(k+1)/2 where k is some positive integer by this we also get that each term will be less than N. This means that we take and iterate over one of the other terms. If we iterate over the first term in increasing order, then we can use two pointers, which gives us a solution in O(Sqrt(N)) .
Implementation:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;#define ll long longint main(){ ll n; cin >> n; ll dig = 2 * n; bool flag= 0; for (ll i = 1; i < sqrt(2 * n + 1); i++) { if (i * i + i > dig) break; ll rest = dig - i * i - i; ll left = 1; ll right = dig; while (left <= right) { ll mid = (left + right) / 2; if (mid * mid + mid > rest) right = mid - 1; else if (mid * mid + mid == rest) { flag = 1; break; } else left = mid + 1; } if (flag) break; } if (flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0;}// this code is contributed by vaibhavsinghii |
Java
// Java implementation of the above approachimport java.util.*;class GFG { public static void main(String[] args) { int n = 24; int dig = 2 * n; boolean flag = false; for (int i = 1; i < Math.sqrt(2 * n + 1); i++) { if (i * i + i > dig) break; int rest = dig - i * i - i; int left = 1; int right = dig; while (left <= right) { int mid = (left + right) / 2; if (mid * mid + mid > rest) right = mid - 1; else if (mid * mid + mid == rest) { flag = true; break; } else left = mid + 1; } if (flag) break; } if (flag) System.out.print("YES"); else System.out.print("NO"); }}// This code is contributed by Rajput-Ji |
Python3
# Python implementation of the above approachimport mathif __name__ == '__main__': n = 24; dig = 2 * n; flag = False; for i in range(1, int(math.sqrt(2 * n + 1))): if (i * i + i > dig): break; rest = dig - i * i - i; left = 1; right = dig; while (left <= right): mid = (left + right) // 2; if (mid * mid + mid > rest): right = mid - 1; elif(mid * mid + mid == rest): flag = True; break; else: left = mid + 1; if (flag): break; if (flag): print("YES"); else: print("NO");# This code is contributed by Rajput-Ji |
C#
// C# implementation of the above approachusing System;public class GFG { public static void Main(String[] args) { int n = 24; int dig = 2 * n; bool flag = false; for (int i = 1; i < Math.Sqrt(2 * n + 1); i++) { if (i * i + i > dig) break; int rest = dig - i * i - i; int left = 1; int right = dig; while (left <= right) { int mid = (left + right) / 2; if (mid * mid + mid > rest) right = mid - 1; else if (mid * mid + mid == rest) { flag = true; break; } else left = mid + 1; } if (flag) break; } if (flag) Console.Write("YES"); else Console.Write("NO"); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript implementation of the above approach var n = 24; var dig = 2 * n; var flag = false; for (i = 1; i < Math.sqrt(2 * n + 1); i++) { if (i * i + i > dig) break; var rest = dig - i * i - i; var left = 1; var right = dig; while (left <= right) { var mid = parseInt((left + right) / 2); if (mid * mid + mid > rest) right = mid - 1; else if (mid * mid + mid == rest) { flag = true; break; } else left = mid + 1; } if (flag) break; } if (flag) document.write("YES"); else document.write("NO");// This code is contributed by Rajput-Ji</script> |
Output
NO
Time Complexity: O(Sqrt(N))
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
