Dado un número entero N, necesitamos encontrar tres números enteros (X, Y, Z) que puedan formar un triángulo con las siguientes condiciones:
- Las longitudes de los lados son números enteros que no exceden N.
- XOR de tres lados es 0, es decir, X ^ Y ^ Z = 0
- El área del triángulo es mayor que 0.
Encuentre todas las ternas posibles que satisfagan las condiciones anteriores.
Ejemplos:
Input: 6
Output: 6 5 3
Input: 10
Output: 10 9 3
6 5 3
Enfoque ingenuo: seleccione el primer lado iterando de N a 1 y luego seleccione el segundo lado iterando desde el primer lado a 1 y luego seleccione el tercer lado iterando desde el segundo lado a 1. Ahora verifique si los tres lados pueden formar un triángulo (la suma de los dos lados más pequeños debe ser mayor que el lado más largo) y la suma xor de longitudes es igual a 0.
Complejidad del tiempo = O(n^3).
Enfoque eficiente: en este método, seleccionamos los dos primeros lados como hicimos en el primer enfoque, el tercer lado será igual al xor de los dos primeros lados (esto hará que la suma xor de longitudes sea igual a 0) y este lado debe ser más pequeño que los dos primeros lados. Ahora comprueba si estos lados pueden formar un triángulo.
Complejidad del tiempo = O(n^2)
C++
// C++ implementation to find all possible
// triangles with XOR of sides zero
#include <bits/stdc++.h>
using namespace std;
// function to find all triples which
// satisfy the necessary condition
void find_all_possible_sides(int n) {
// selects first side
for (int x = n; x > 0; x--) {
// select second side
for (int y = x - 1; y >= 0; y--) {
// third side is equal to xor of
// first and second side
int z = x ^ y;
if (z < x && z < y) {
// find longest side
int max_side = max(x, max(y, z));
// check if it can make a triangle
if (x + y + z - max_side > max_side) {
cout << x << " " << y << " "
<< z << endl;
}
}
}
}
}
// Driver Program
int main() {
int n = 10;
find_all_possible_sides(n);
return 0;
}
Java
// Java implementation to find all possible
// triangles with XOR of sides zero
import java.lang.*;
class GFG {
// function to find all triples which
// satisfy the necessary condition
static void find_all_possible_sides(int n) {
// selects first side
for (int x = n; x > 0; x--) {
// select second side
for (int y = x - 1; y >= 0; y--) {
// third side is equal to xor of
// first and second side
int z = x ^ y;
if (z < x && z < y) {
// find longest side
int max_side = Math.max(x, Math.max(y, z));
// check if it can make a triangle
if (x + y + z - max_side > max_side) {
System.out.println(x + " " + y + " " + z);
}
}
}
}
}
// Driver code
public static void main(String[] args) {
int n = 10;
find_all_possible_sides(n);
}
}
// This code is contributed by Anant Agarwal.
Python3
# function to find # all triples which # satisfy the necessary condition def find_all_possible_sides(n): # selects first side for x in range(n,0,-1): # select second side for y in range(x - 1,-1,-1): # third side is equal to xor of # first and second side z = x ^ y if (z < x and z < y): # find longest side max_side =max(x,max(y, z)) # check if it can make a triangle if (x + y + z - max_side > max_side): print(x , " " , y , " ", z) # driver code n = 10 find_all_possible_sides(n) # This code is contributed # by Anant Agarwal.
C#
// C# implementation to find all possible
// triangles with XOR of sides zero
using System;
class GFG {
// function to find all triples which
// satisfy the necessary condition
static void find_all_possible_sides(int n) {
// selects first side
for (int x = n; x > 0; x--) {
// select second side
for (int y = x - 1; y >= 0; y--) {
// third side is equal to xor of
// first and second side
int z = x ^ y;
if (z < x && z < y) {
// find longest side
int max_side = Math.Max(x,
Math.Max(y, z));
// check if it can make a
// triangle
if (x + y + z - max_side >
max_side) {
Console.WriteLine(x + " "
+ y + " " + z);
}
}
}
}
}
// Driver code
public static void Main() {
int n = 10;
find_all_possible_sides(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP implementation to find all possible
// triangles with XOR of sides zero
// function to find all triples which
// satisfy the necessary condition
function find_all_possible_sides($n) {
// selects first side
for ($x = $n; $x > 0; $x--) {
// select second side
for ($y = $x - 1; $y >= 0; $y--) {
// third side is equal to xor of
// first and second side
$z = $x ^ $y;
if ($z < $x && $z < $y) {
// find longest side
$max_side = max($x, max($y, $z));
// check if it can make a triangle
if ($x + $y + $z - $max_side > $max_side)
{
echo $x , " " ,$y , " ",
$z ,"\n" ;
}
}
}
}
}
// Driver Code
$n = 10;
find_all_possible_sides($n);
// This code is contributed by anuj_67
?>
Javascript
<script>
// Javascript implementation to find all possible
// triangles with XOR of sides zero
// function to find all triples which
// satisfy the necessary condition
function find_all_possible_sides(n) {
// selects first side
for (let x = n; x > 0; x--) {
// select second side
for (let y = x - 1; y >= 0; y--) {
// third side is equal to xor of
// first and second side
let z = x ^ y;
if (z < x && z < y) {
// find longest side
let max_side = Math.max(x, Math.max(y, z));
// check if it can make a triangle
if (x + y + z - max_side > max_side) {
document.write(x + " " + y + " "
+ z + "<br>");
}
}
}
}
}
// Driver Program
let n = 10;
find_all_possible_sides(n);
</script>
Producción:
10 9 3 6 5 3
Publicación traducida automáticamente
Artículo escrito por Gautam Karakoti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA