Given an positive integer N, the task is to find the number of triplets (X, Y, Z) such that the sum of product of any two numbers with the third number is N.
Examples:
Input: N = 2
Output: 1
Explanation:
The only triplets satisfying the given criteria is (1, 1, 1). Therefore, the count is 1.Input: N = 3
Output: 3
Approach: This given problem can be solved by rearranging the equation as:
Consider a triplet as (X, Y, Z) then
=>
=>
From the above equation the idea is to iterate over all possible value of Z over the range [1, N] and add the count of all possible of X and Y by calculating the prime factor of (N – Z) satisfying the above equation. Follow the below steps to solve the problem:
- Initialize a variable, countTriplets to store the resultant count of triplets satisfying the given criteria.
- Find the smallest prime factor for all the elements over the range [1, 105] using the Sieve Of Eratosthenes.
- Iterate over the range [1, N] using the variable, say K and perform the following steps:
- Find the number of pairs of whose product is (N – K) using the approach discussed in this article and add the count obtained to the variable countTriplets.
- After completing the above steps, print the value of countTriplets as the resultant count of triplets.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;vector<int> s(11,0);// Function to find the SPF[i] using the// Sieve Of Eratosthenesvoid sieveOfEratosthenes(int N){ // Stores whether i is prime or not bool prime[N+1]; memset(prime,false,sizeof(false)); // Initializing smallest factor as // 2 for all even numbers for (int i=2;i< N + 1; i+=2) s[i] = 2; // Iterate for all odd numbers < N for(int i =3;i<N + 1;i+=2){ if (prime[i] == false){ // SPF of i for a prime is // the number itself s[i] = i; // Iterate for all the multiples // of the current prime number for(int j= i;j< N / i + 1; j+=2){ if (prime[i * j] == false){ prime[i * j] = true; // The value i is smallest // prime factor for i * j s[i * j] = i; } } } }}// Function to generate prime factors// and its powerint generatePrimeFactors(int N){ // Current prime factor of N int curr = s[N]; // Stores the powers of the current // prime factor map<int,int> cnt; cnt[s[N]] = 1; // Find all the prime factors and // their powers while (N > 1){ N /= s[N]; if (N and s[N]) if(cnt.find(s[N]) == cnt.end()) cnt[s[N]] = 1; else cnt[s[N]] += 1; } if (cnt.find(0) != cnt.end()) cnt.erase(0); int totfactor = 1; for (auto i: cnt) totfactor *= i.second + 1; // Return the total count of factors return totfactor; } // Function to count the number of triplets// satisfying the given criteriaint countTriplets(int N){ // Stores the count of resultant triplets int CountTriplet = 0; for (int z=1;z<N + 1;z++){ // Add the count all factors of N-z // to the variable CountTriplet int p = generatePrimeFactors(N-z); if (p > 1) CountTriplet += p; } // Return total count of triplets return CountTriplet + 1; }// Driver Codeint main(){int N = 10;// S[i] stores the smallest prime factor// for each element i// Find the SPF[i]sieveOfEratosthenes(N);// Function Callcout<<countTriplets(N);}// This code is contributed by SURENDRA_GANGWAR. |
Java
// Java program for the above approachimport java.util.*;class GFG{static int[] s = new int[11];// Function to find the SPF[i] using the// Sieve Of Eratosthenesstatic void sieveOfEratosthenes(int N){ // Stores whether i is prime or not boolean []prime = new boolean[N+1]; // Initializing smallest factor as // 2 for all even numbers for (int i = 2; i < N + 1; i += 2) s[i] = 2; // Iterate for all odd numbers < N for(int i = 3; i < N + 1; i += 2){ if (prime[i] == false){ // SPF of i for a prime is // the number itself s[i] = i; // Iterate for all the multiples // of the current prime number for(int j= i; j < N / i + 1; j += 2){ if (prime[i * j] == false){ prime[i * j] = true; // The value i is smallest // prime factor for i * j s[i * j] = i; } } } }}// Function to generate prime factors// and its powerstatic int generatePrimeFactors(int N){ // Current prime factor of N int curr = s[N]; // Stores the powers of the current // prime factor HashMap<Integer,Integer> cnt = new HashMap<>(); cnt.put(s[N],1); // Find all the prime factors and // their powers while (N > 1){ N /= s[N]; if (N != 0 && s[N] != 0) if(!cnt.containsKey(s[N])) cnt.put(s[N], 1); else cnt.put(s[N], cnt.get(s[N]) + 1); } if (cnt.containsKey(0)) cnt.remove(0); int totfactor = 1; for (Map.Entry<Integer,Integer> i : cnt.entrySet()) totfactor *= i.getValue() + 1; // Return the total count of factors return totfactor; } // Function to count the number of triplets// satisfying the given criteriastatic int countTriplets(int N){ // Stores the count of resultant triplets int CountTriplet = 0; for (int z=1;z<N + 1;z++){ // Add the count all factors of N-z // to the variable CountTriplet int p = generatePrimeFactors(N-z); if (p > 1) CountTriplet += p; } // Return total count of triplets return CountTriplet + 1; }// Driver Codepublic static void main(String[] args){int N = 10;// S[i] stores the smallest prime factor// for each element i// Find the SPF[i]sieveOfEratosthenes(N);// Function CallSystem.out.print(countTriplets(N));}}// This code is contributed by gauravrajput1 |
Python3
# Python program for the above approach# Function to find the SPF[i] using the# Sieve Of Eratosthenesdef sieveOfEratosthenes(N, s): # Stores whether i is prime or not prime = [False] * (N + 1) # Initializing smallest factor as # 2 for all even numbers for i in range(2, N + 1, 2): s[i] = 2 # Iterate for all odd numbers < N for i in range(3, N + 1, 2): if (prime[i] == False): # SPF of i for a prime is # the number itself s[i] = i # Iterate for all the multiples # of the current prime number for j in range(i, int(N / i) + 1, 2): if (prime[i * j] == False): prime[i * j] = True # The value i is smallest # prime factor for i * j s[i * j] = i# Function to generate prime factors# and its powerdef generatePrimeFactors(N): # Current prime factor of N curr = s[N] # Stores the powers of the current # prime factor cnt = {s[N]:1} # Find all the prime factors and # their powers while (N > 1): N //= s[N] if N and s[N]: if cnt.get(s[N], 0) == 0: cnt[s[N]] = 1 else: cnt[s[N]] += 1 if 0 in cnt: cnt.pop(0) totfactor = 1 for i in cnt.values(): totfactor *= i + 1 # Return the total count of factors return totfactor # Function to count the number of triplets# satisfying the given criteriadef countTriplets(N): # Stores the count of resultant triplets CountTriplet = 0 for z in range(1, N + 1): # Add the count all factors of N-z # to the variable CountTriplet p = generatePrimeFactors(N-z) if p > 1: CountTriplet += p # Return total count of triplets return CountTriplet + 1 # Driver CodeN = 10# S[i] stores the smallest prime factor# for each element is = [0] * (N + 1)# Find the SPF[i]sieveOfEratosthenes(N, s)# Function Callprint(countTriplets(N)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ static int[] s = new int[11]; // Function to find the SPF[i] using the // Sieve Of Eratosthenes static void sieveOfEratosthenes(int N) { // Stores whether i is prime or not bool[] prime = new bool[N + 1]; // Initializing smallest factor as // 2 for all even numbers for (int i = 2; i < N + 1; i += 2) s[i] = 2; // Iterate for all odd numbers < N for (int i = 3; i < N + 1; i += 2) { if (prime[i] == false) { // SPF of i for a prime is // the number itself s[i] = i; // Iterate for all the multiples // of the current prime number for (int j = i; j < N / i + 1; j += 2) { if (prime[i * j] == false) { prime[i * j] = true; // The value i is smallest // prime factor for i * j s[i * j] = i; } } } } } // Function to generate prime factors // and its power static int generatePrimeFactors(int N) { // Current prime factor of N // int curr = s[N]; // Stores the powers of the current // prime factor Dictionary<int, int> cnt = new Dictionary<int, int>(); cnt.Add(s[N], 1); // Find all the prime factors and // their powers while (N > 1) { N /= s[N]; if (N != 0 && s[N] != 0) if (!cnt.ContainsKey(s[N])) cnt.Add(s[N], 1); else cnt[s[N]]++; } if(cnt.ContainsKey(0)) cnt.Remove(0); int totfactor = 1; // get the factor count and multiply them foreach (var entry in cnt) totfactor *= entry.Value + 1; // Return the total count of factors return totfactor; } // Function to count the number of triplets // satisfying the given criteria static int countTriplets(int N) { // Stores the count of resultant triplets int countTriplet = 0; for (int z = 1; z < N + 1; z++) { // Add the count all factors of N-z // to the variable CountTriplet int p = generatePrimeFactors(N - z); if (p > 1) countTriplet += p; } // Return total count of triplets return countTriplet + 1; } static void Main(string[] args) { int N = 10; // Find the SPF[i] sieveOfEratosthenes(N); // Function Call Console.WriteLine(countTriplets(N)); } } |
Javascript
<script>// Javascript program for the above approachlet s = new Array(11).fill(0)// Function to find the SPF[i] using the// Sieve Of Eratosthenesfunction sieveOfEratosthenes(N){ // Stores whether i is prime or not let prime = new Array(N+1).fill(false); // Initializing smallest factor as // 2 for all even numbers for (let i = 2; i < N + 1; i += 2) s[i] = 2; // Iterate for all odd numbers < N for(let i = 3; i < N + 1; i += 2){ if (prime[i] == false){ // SPF of i for a prime is // the number itself s[i] = i; // Iterate for all the multiples // of the current prime number for(let j= i; j < Math.floor(N / i + 1); j += 2){ if (prime[i * j] == false){ prime[i * j] = true; // The value i is smallest // prime factor for i * j s[i * j] = i; } } } }}// Function to generate prime factors// and its powerfunction generatePrimeFactors(N){ // Current prime factor of N let curr = s[N]; // Stores the powers of the current // prime factor let cnt = new Map(); cnt.set(s[N],1); // Find all the prime factors and // their powers while (N > 1){ N = Math.floor(N / s[N]); if (N != 0 && s[N] != 0) if(!cnt.has(s[N])) cnt.set(s[N], 1); else cnt.set(s[N], cnt.get(s[N]) + 1); } if (cnt.has(0)) cnt.delete(0); let totfactor = 1; for (i of cnt.values()) totfactor *= i + 1; // Return the total count of factors return totfactor; } // Function to count the number of triplets// satisfying the given criteriafunction countTriplets(N){ // Stores the count of resultant triplets let CountTriplet = 0; for (let z=1;z<N + 1;z++){ // Add the count all factors of N-z // to the variable CountTriplet let p = generatePrimeFactors(N-z); if (p > 1) CountTriplet += p; } // Return total count of triplets return CountTriplet + 1; }// Driver Codelet N = 10;// S[i] stores the smallest prime factor// for each element i// Find the SPF[i]sieveOfEratosthenes(N);// Function Calldocument.write((countTriplets(N)));// This code is contributed by _saurabh_jaiswal</script> |
Output:
23
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
