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

Опубликовано: 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.

Technical Scripter Олимпиады по программированию Алгоритмы Структуры данных

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

C ++

Джава

Python3

C #

Javascript

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