Найдите различные целые числа для тройки с заданным продуктом

Опубликовано: 5 Января, 2022

Учитывая целое число X , задача состоит в том, чтобы найти три различных целых числа больше 1, то есть A , B и C, такие, что (A * B * C) = X. Если такой тройки не существует, выведите -1 .
Примеры:

Input: X = 64 
Output: 2 4 8 
(2 * 4 * 8) = 64
Input: X = 32 
Output: -1 
No such triplet exists. 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: предположим, что у нас есть тройка (A, B, C) . Обратите внимание, что для того, чтобы их произведение было равно X , каждое целое число должно быть множителем X. Итак, сохраните все факторы X в O (sqrt (X)) времени, используя подход, обсуждаемый в этой статье.
Теперь множителей sqrt (X) будет не больше. Затем выполните итерацию по каждому фактору, запустив два цикла: один выбирает A, а другой выбирает B. Теперь, если эта тройка действительна, то есть C = X / (A * B), где C также является фактором X. Чтобы проверить это, сохраните все факторы в unordered_set. Если действительный триплет найден, то выведите триплет, иначе выведите -1 .
Ниже представлена реализация описанного выше подхода:

C ++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the required triplets
void findTriplets( int x)
{
// To store the factors
vector< int > fact;
unordered_set< int > factors;
// Find factors in sqrt(x) time
for ( int i = 2; i <= sqrt (x); i++) {
if (x % i == 0) {
fact.push_back(i);
if (x / i != i)
fact.push_back(x / i);
factors.insert(i);
factors.insert(x / i);
}
}
bool found = false ;
int k = fact.size();
for ( int i = 0; i < k; i++) {
// Choose a factor
int a = fact[i];
for ( int j = 0; j < k; j++) {
// Choose another factor
int b = fact[j];
// These conditions need to be
// met for a valid triplet
if ((a != b) && (x % (a * b) == 0)
&& (x / (a * b) != a)
&& (x / (a * b) != b)
&& (x / (a * b) != 1)) {
// Print the valid triplet
cout << a << " " << b << " "
<< (x / (a * b));
found = true ;
break ;
}
}
// Triplet found
if (found)
break ;
}
// Triplet not found
if (!found)
cout << "-1" ;
}
// Driver code
int main()
{
int x = 105;
findTriplets(x);
return 0;
}

Джава

// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to find the required triplets
static void findTriplets( int x)
{
// To store the factors
Vector<Integer> fact = new Vector<Integer>();
HashSet<Integer> factors = new HashSet<Integer>();
// Find factors in Math.sqrt(x) time
for ( int i = 2 ; i <= Math.sqrt(x); i++)
{
if (x % i == 0 )
{
fact.add(i);
if (x / i != i)
fact.add(x / i);
factors.add(i);
factors.add(x / i);
}
}
boolean found = false ;
int k = fact.size();
for ( int i = 0 ; i < k; i++)
{
// Choose a factor
int a = fact.get(i);
for ( int j = 0 ; j < k; j++)
{
// Choose another factor
int b = fact.get(j);
// These conditions need to be
// met for a valid triplet
if ((a != b) && (x % (a * b) == 0 )
&& (x / (a * b) != a)
&& (x / (a * b) != b)
&& (x / (a * b) != 1 ))
{
// Print the valid triplet
System.out.print(a+ " " + b + " "
+ (x / (a * b)));
found = true ;
break ;
}
}
// Triplet found
if (found)
break ;
}
// Triplet not found
if (!found)
System.out.print( "-1" );
}
// Driver code
public static void main(String[] args)
{
int x = 105 ;
findTriplets(x);
}
}
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
from math import sqrt
# Function to find the required triplets
def findTriplets(x) :
# To store the factors
fact = [];
factors = set ();
# Find factors in sqrt(x) time
for i in range ( 2 , int (sqrt(x))) :
if (x % i = = 0 ) :
fact.append(i);
if (x / i ! = i) :
fact.append(x / / i);
factors.add(i);
factors.add(x / / i);
found = False ;
k = len (fact);
for i in range (k) :
# Choose a factor
a = fact[i];
for j in range (k) :
# Choose another factor
b = fact[j];
# These conditions need to be
# met for a valid triplet
if ((a ! = b) and (x % (a * b) = = 0 )
and (x / (a * b) ! = a)
and (x / (a * b) ! = b)
and (x / (a * b) ! = 1 )) :
# Print the valid triplet
print (a,b,x / / (a * b));
found = True ;
break ;
# Triplet found
if (found) :
break ;
# Triplet not found
if ( not found) :
print ( "-1" );
# Driver code
if __name__ = = "__main__" :
x = 105 ;
findTriplets(x);
# This code is contributed by AnkitRai01

C #

// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the required triplets
static void findTriplets( int x)
{
// To store the factors
List< int > fact = new List< int >();
HashSet< int > factors = new HashSet< int >();
// Find factors in Math.Sqrt(x) time
for ( int i = 2; i <= Math.Sqrt(x); i++)
{
if (x % i == 0)
{
fact.Add(i);
if (x / i != i)
fact.Add(x / i);
factors.Add(i);
factors.Add(x / i);
}
}
bool found = false ;
int k = fact.Count;
for ( int i = 0; i < k; i++)
{
// Choose a factor
int a = fact[i];
for ( int j = 0; j < k; j++)
{
// Choose another factor
int b = fact[j];
// These conditions need to be
// met for a valid triplet
if ((a != b) && (x % (a * b) == 0)
&& (x / (a * b) != a)
&& (x / (a * b) != b)
&& (x / (a * b) != 1))
{
// Print the valid triplet
Console.Write(a+ " " + b + " "
+ (x / (a * b)));
found = true ;
break ;
}
}
// Triplet found
if (found)
break ;
}
// Triplet not found
if (!found)
Console.Write( "-1" );
}
// Driver code
public static void Main(String[] args)
{
int x = 105;
findTriplets(x);
}
}
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript implementation of the approach
// Function to find the required triplets
function findTriplets(x)
{
// To store the factors
let fact = [];
let factors = new Set();
// Find factors in Math.sqrt(x) time
for (let i = 2; i <= Math.sqrt(x); i++)
{
if (x % i == 0)
{
fact.push(i);
if (x / i != i)
fact.push(x / i);
factors.add(i);
factors.add(x / i);
}
}
let found = false ;
let k = fact.length;
for (let i = 0; i < k; i++)
{
// Choose a factor
let a = fact[i];
for (let j = 0; j < k; j++)
{
// Choose another factor
let b = fact[j];
// These conditions need to be
// met for a valid triplet
if ((a != b) && (x % (a * b) == 0)
&& (x / (a * b) != a)
&& (x / (a * b) != b)
&& (x / (a * b) != 1))
{
// Prlet the valid triplet
document.write(a+ " " + b + " "
+ (x / (a * b)));
found = true ;
break ;
}
}
// Triplet found
if (found)
break ;
}
// Triplet not found
if (!found)
document.write( "-1" );
}
// Driver code
let x = 105;
findTriplets(x);
</script>
Выход:
 3 5 7

Сложность времени: O (N), N = X

Вспомогательное пространство: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ