Given a number N. Print three distinct numbers (>=1) whose product is equal to N. print -1 if it is not possible to find three numbers.
Examples:
Input: 64
Output: 2 4 8
Explanation:
(2*4*8 = 64)
Input: 24
Output: 2 3 4
Explanation:
(2*3*4 = 24)
Input: 12
Output: -1
Explanation:
No such triplet exists
Approach:
- Make an array which stores all the divisors of the given number using the approach discussed in this article
- Let the three number be a, b, c initialize to 1
- Traverse the divisors array and check the following condition:
- value of a = value at 1st index of divisor array.
- value of b = product of value at 2nd and 3rd index of divisor array. If divisor array has only one or two elements then no such triplets exists
- After finding a & b, value of c = product of all the rest elements in divisor array.
- Check the final condition such that value of a, b, c must be distinct and not equal to 1.
Below is the implementation code:
CPP
// C++ program to find the// three numbers#include "bits/stdc++.h"using namespace std;// function to find 3 distinct number// with given productvoid getnumbers(int n){ // Declare a vector to store // divisors vector<int> divisor; // store all divisors of number // in array for (int i = 2; i * i <= n; i++) { // store all the occurrence of // divisors while (n % i == 0) { divisor.push_back(i); n /= i; } } // check if n is not equals to -1 // then n is also a prime factor if (n != 1) { divisor.push_back(n); } // Initialize the variables with 1 int a, b, c, size; a = b = c = 1; size = divisor.size(); for (int i = 0; i < size; i++) { // check for first number a if (a == 1) { a = a * divisor[i]; } // check for second number b else if (b == 1 || b == a) { b = b * divisor[i]; } // check for third number c else { c = c * divisor[i]; } } // check for all unwanted condition if (a == 1 || b == 1 || c == 1 || a == b || b == c || a == c) { cout << "-1" << endl; } else { cout << a << ' ' << b << ' ' << c << endl; }}// Driver functionint main(){ int n = 64; getnumbers(n);} |
Java
// Java program to find the// three numbersimport java.util.*;class GFG{ // function to find 3 distinct number// with given productstatic void getnumbers(int n){ // Declare a vector to store // divisors Vector<Integer> divisor = new Vector<Integer>(); // store all divisors of number // in array for (int i = 2; i * i <= n; i++) { // store all the occurrence of // divisors while (n % i == 0) { divisor.add(i); n /= i; } } // check if n is not equals to -1 // then n is also a prime factor if (n != 1) { divisor.add(n); } // Initialize the variables with 1 int a, b, c, size; a = b = c = 1; size = divisor.size(); for (int i = 0; i < size; i++) { // check for first number a if (a == 1) { a = a * divisor.get(i); } // check for second number b else if (b == 1 || b == a) { b = b * divisor.get(i); } // check for third number c else { c = c * divisor.get(i); } } // check for all unwanted condition if (a == 1 || b == 1 || c == 1 || a == b || b == c || a == c) { System.out.print("-1" +"\n"); } else { System.out.print(a +" "+ b +" "+ c +"\n"); }} // Driver functionpublic static void main(String[] args){ int n = 64; getnumbers(n);}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to find the# three numbers# function to find 3 distinct number# with given productdef getnumbers(n): # Declare a vector to store # divisors divisor = [] # store all divisors of number # in array for i in range(2, n + 1): # store all the occurrence of # divisors while (n % i == 0): divisor.append(i) n //= i # check if n is not equals to -1 # then n is also a prime factor if (n != 1): divisor.append(n) # Initialize the variables with 1 a, b, c, size = 0, 0, 0, 0 a = b = c = 1 size = len(divisor) for i in range(size): # check for first number a if (a == 1): a = a * divisor[i] # check for second number b elif (b == 1 or b == a): b = b * divisor[i] # check for third number c else: c = c * divisor[i] # check for all unwanted condition if (a == 1 or b == 1 or c == 1 or a == b or b == c or a == c): print("-1") else: print(a, b, c)# Driver functionn = 64getnumbers(n)# This code is contributed by mohit kumar 29 |
C#
// C# program to find the// three numbersusing System;using System.Collections.Generic;class GFG{ // function to find 3 distinct number// with given productstatic void getnumbers(int n){ // Declare a vector to store // divisors List<int> divisor = new List<int>(); // store all divisors of number // in array for (int i = 2; i * i <= n; i++) { // store all the occurrence of // divisors while (n % i == 0) { divisor.Add(i); n /= i; } } // check if n is not equals to -1 // then n is also a prime factor if (n != 1) { divisor.Add(n); } // Initialize the variables with 1 int a, b, c, size; a = b = c = 1; size = divisor.Count; for (int i = 0; i < size; i++) { // check for first number a if (a == 1) { a = a * divisor[i]; } // check for second number b else if (b == 1 || b == a) { b = b * divisor[i]; } // check for third number c else { c = c * divisor[i]; } } // check for all unwanted condition if (a == 1 || b == 1 || c == 1 || a == b || b == c || a == c) { Console.Write("-1" +"\n"); } else { Console.Write(a +" "+ b +" "+ c +"\n"); }} // Driver functionpublic static void Main(String[] args){ int n = 64; getnumbers(n);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to find the// three numbers// function to find 3 distinct number// with given productfunction getnumbers(n){ // Declare a vector to store // divisors let divisor = []; // store all divisors of number // in array for (let i = 2; i * i <= n; i++) { // store all the occurrence of // divisors while (n % i == 0) { divisor.push(i); n = Math.floor(n/i); } } // check if n is not equals to -1 // then n is also a prime factor if (n != 1) { divisor.push(n); } // Initialize the variables with 1 let a, b, c, size; a = b = c = 1; size = divisor.length; for (let i = 0; i < size; i++) { // check for first number a if (a == 1) { a = a * divisor[i]; } // check for second number b else if (b == 1 || b == a) { b = b * divisor[i]; } // check for third number c else { c = c * divisor[i]; } } // check for all unwanted condition if (a == 1 || b == 1 || c == 1 || a == b || b == c || a == c) { document.write("-1" +"<br>"); } else { document.write(a +" "+ b +" "+ c +"<br>"); }}// Driver functionlet n = 64;getnumbers(n);// This code is contributed by patel2127</script> |
2 4 8
Time Complexity: O((log N)*sqrt(N))
Auxiliary Space: O(sqrt(n))
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More Information here to that Topic: geeksforgeeks.org/check-if-n-can-be-expressed-as-product-of-3-distinct-numbers/ […]
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/check-if-n-can-be-expressed-as-product-of-3-distinct-numbers/ […]
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/check-if-n-can-be-expressed-as-product-of-3-distinct-numbers/ […]