Dado un número entero N , la tarea es averiguar si se puede escribir como una suma de 2 números triangulares (que pueden ser distintos o no).
Ejemplos:
Input: N = 24 Output: YES 24 can be represented as 3+21. Input: N = 15 Output: NO
Enfoque:
Considere todos los números triangulares menores que N , es decir, números sqrt(N). Vamos a agregarlos a un conjunto, y para cada número triangular X verificamos si NX está presente en el conjunto. Si es cierto con cualquier número triangular, entonces la respuesta es SÍ, de lo contrario, la respuesta es NO.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible or not
bool 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 Code
int main()
{
int n = 24;
checkTriangularSumRepresentation(n) ? cout << "Yes"
: cout << "No";
return 0;
}
Java
// Java implementation of the approach
import 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 approach
using 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 not
function 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 Code
var n = 24;
checkTriangularSumRepresentation(n) ? document.write( "Yes")
: document.write( "No");
// This code is contributed by famously.
</script>
Producción:
Yes
Complejidad del tiempo: O(Sqrt(N))
Espacio auxiliar: O(sqrt(N))
Segundo enfoque: está muy claro que N es positivo porque los números triangulares son números que se pueden representar como k*(k+1)/2 donde k es un número entero positivo con esto también obtenemos que cada término será menor que N. Esto significa que tomamos e iteramos sobre uno de los otros términos. Si iteramos sobre el primer término en orden creciente, entonces podemos usar dos punteros, lo que nos da una solución en O(Sqrt(N)) .
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int 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 approach
import 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 approach
import math
if __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 approach
using 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>
Producción:
YES
Complejidad del tiempo: O(Sqrt(N))
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA