Given two natural numbers N and M, Create a graph using these two natural numbers using relation that a number is connected to its largest factor other than itself. The task is to find the shortest path between these two numbers after creating a graph.
Examples:
Input: N = 6, M = 18
Output: 6 <–> 3 <–> 9 <–> 18
Explanation:
For N = 6, the connection of graph is:
6 — 3 — 1
For N = 18, the connection of graph is:
18 — 9 — 3 — 1
Combining the above two graphs, the shortest path is given by:
6 — 3 — 9 — 18Input: N = 4, M = 8
Output: 4 <–> 8
Approach: The idea is to find the largest factors of each number other than itself and create a graph by connecting these factors and then find the shortest path between them. Below are the steps:
- Find the largest common factor of M and store it and set it as M.
- Now, until M doesn’t equal to 1 keep repeating the above steps and store the factors generated in an array mfactor[].
- Repeat step 1 and step 2 by taking N as the number and store the factors generated in an array nfactor[].
- Now, traverse both the arrays mfactor[] and mfactor[] and print the shortest path.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check the number is// prime or notint isprm(int n){ // Base Cases if (n <= 1) return 0; if (n <= 3) return 1; if (n % 2 == 0 || n % 3 == 0) return 0; // Iterate till [5, sqrt(N)] to // detect primarility of numbers for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return 0; return 1;}// Function to print the shortest pathvoid shortestpath(int m, int n){ // Use vector to store the factor // of m and n vector<int> mfactor, nfactor; // Use map to check if largest common // factor previously present or not map<int, int> fre; // First store m mfactor.push_back(m); fre[m] = 1; while (m != 1) { // Check whether m is prime or not if (isprm(m)) { mfactor.push_back(1); fre[1] = 1; m = 1; } // Largest common factor of m else { for (int i = 2; i <= sqrt(m); i++) { // If m is divisible by i if (m % i == 0) { // Store the largest // common factor mfactor.push_back(m / i); fre[m / i] = 1; m = (m / i); break; } } } } // For number n nfactor.push_back(n); while (fre[n] != 1) { // Check whether n is prime if (isprm(n)) { nfactor.push_back(1); n = 1; } // Largest common factor of n else { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { // Store the largest // common factor nfactor.push_back(n / i); n = (n / i); break; } } } } // Print the path // Print factors from m for (int i = 0; i < mfactor.size(); i++) { // To avoid duplicate printing // of same element if (mfactor[i] == n) break; cout << mfactor[i] << " <--> "; } // Print the factors from n for (int i = nfactor.size() - 1; i >= 0; i--) { if (i == 0) cout << nfactor[i]; else cout << nfactor[i] << " <--> "; }}// Driver Codeint main(){ // Given N and M int m = 18, n = 19; // Function Call shortestpath(m, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check the number is// prime or notstatic int isprm(int n){ // Base Cases if (n <= 1) return 0; if (n <= 3) return 1; if (n % 2 == 0 || n % 3 == 0) return 0; // Iterate till [5, Math.sqrt(N)] to // detect primarility of numbers for(int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return 0; return 1;}// Function to print the shortest pathstatic void shortestpath(int m, int n){ // Use vector to store the factor // of m and n Vector<Integer> mfactor = new Vector<>(); Vector<Integer> nfactor = new Vector<>(); // Use map to check if largest common // factor previously present or not HashMap<Integer, Integer> fre = new HashMap<>(); // First store m mfactor.add(m); fre.put(m, 1); while (m != 1) { // Check whether m is prime or not if (isprm(m) != 0) { mfactor.add(1); fre.put(1, 1); m = 1; } // Largest common factor of m else { for(int i = 2; i <= Math.sqrt(m); i++) { // If m is divisible by i if (m % i == 0) { // Store the largest // common factor mfactor.add(m / i); fre.put(m / i, 1); m = (m / i); break; } } } } // For number n nfactor.add(n); while (fre.containsKey(n) && fre.get(n) != 1) { // Check whether n is prime if (isprm(n) != 0) { nfactor.add(1); n = 1; } // Largest common factor of n else { for(int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { // Store the largest // common factor nfactor.add(n / i); n = (n / i); break; } } } } // Print the path // Print factors from m for(int i = 0; i < mfactor.size(); i++) { // To astatic void duplicate printing // of same element if (mfactor.get(i) == n) break; System.out.print(mfactor.get(i) + " <--> "); } // Print the factors from n for(int i = nfactor.size() - 1; i >= 0; i--) { if (i == 0) System.out.print(nfactor.get(i)); else System.out.print(nfactor.get(i) + " <--> "); }}// Driver Codepublic static void main(String[] args){ // Given N and M int m = 18, n = 19; // Function call shortestpath(m, n);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachimport math# Function to check the number is# prime or notdef isprm(n): # Base Cases if (n <= 1): return 0 if (n <= 3): return 1 if (n % 2 == 0 or n % 3 == 0): return 0 # Iterate till [5, sqrt(N)] to # detect primarility of numbers i = 5 while i * i <= n: if (n % i == 0 or n % (i + 2) == 0): return 0 i += 6 return 1# Function to print the shortest pathdef shortestpath(m, n): # Use vector to store the factor # of m and n mfactor = [] nfactor = [] # Use map to check if largest common # factor previously present or not fre = dict.fromkeys(range(n + 1), 0) # First store m mfactor.append(m) fre[m] = 1 while (m != 1): # Check whether m is prime or not if (isprm(m)): mfactor.append(1) fre[1] = 1 m = 1 # Largest common factor of m else: sqt = (int)(math.sqrt(m)) for i in range(2, sqt + 1): # If m is divisible by i if (m % i == 0): # Store the largest # common factor mfactor.append(m // i) fre[m // i] = 1 m = (m // i) break # For number n nfactor.append(n) while (fre[n] != 1): # Check whether n is prime if (isprm(n)): nfactor.append(1) n = 1 # Largest common factor of n else: sqt = (int)(math.sqrt(n)) for i in range(2, sqt + 1): if (n % i == 0): # Store the largest # common factor nfactor.append(n // i) n = (n // i) break # Print the path # Print factors from m for i in range(len(mfactor)): # To avoid duplicate printing # of same element if (mfactor[i] == n): break print(mfactor[i], end = " <--> ") # Print the factors from n for i in range(len(nfactor) - 1, -1, -1): if (i == 0): print (nfactor[i], end = "") else: print(nfactor[i], end = " <--> ") # Driver Codeif __name__ == "__main__": # Given N and M m = 18 n = 19 # Function call shortestpath(m, n)# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to check the number is// prime or notstatic int isprm(int n){ // Base Cases if (n <= 1) return 0; if (n <= 3) return 1; if (n % 2 == 0 || n % 3 == 0) return 0; // Iterate till [5, Math.Sqrt(N)] to // detect primarility of numbers for(int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return 0; return 1;}// Function to print the shortest pathstatic void shortestpath(int m, int n){ // Use vector to store the factor // of m and n List<int> mfactor = new List<int>(); List<int> nfactor = new List<int>(); // Use map to check if largest common // factor previously present or not Dictionary<int, int> fre = new Dictionary<int, int>(); // First store m mfactor.Add(m); fre.Add(m, 1); while (m != 1) { // Check whether m is prime or not if (isprm(m) != 0) { mfactor.Add(1); if(!fre.ContainsKey(1)) fre.Add(1, 1); m = 1; } // Largest common factor of m else { for(int i = 2; i <= Math.Sqrt(m); i++) { // If m is divisible by i if (m % i == 0) { // Store the largest // common factor mfactor.Add(m / i); if(!fre.ContainsKey(m/i)) fre.Add(m / i, 1); m = (m / i); break; } } } } // For number n nfactor.Add(n); while (fre.ContainsKey(n) && fre[n] != 1) { // Check whether n is prime if (isprm(n) != 0) { nfactor.Add(1); n = 1; } // Largest common factor of n else { for(int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { // Store the largest // common factor nfactor.Add(n / i); n = (n / i); break; } } } } // Print the path // Print factors from m for(int i = 0; i < mfactor.Count; i++) { // To astatic void duplicate printing // of same element if (mfactor[i] == n) break; Console.Write(mfactor[i] + " <--> "); } // Print the factors from n for(int i = nfactor.Count - 1; i >= 0; i--) { if (i == 0) Console.Write(nfactor[i]); else Console.Write(nfactor[i] + " <--> "); }}// Driver Codepublic static void Main(String[] args){ // Given N and M int m = 18, n = 19; // Function call shortestpath(m, n);}}// This code is contributed by 29AjayKumar |
Javascript
// Javascript program for the above approach// Function to check the number is// prime or notfunction isprm(n){ // Base Cases if (n <= 1) return 0; if (n <= 3) return 1; if (n % 2 == 0 || n % 3 == 0) return 0; // Iterate till [5, sqrt(N)] to // detect primarility of numbers for (let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return 0; return 1;}// Function to print the shortest pathfunction shortestpath(m, n){ // Use vector to store the factor // of m and n let mfactor = new Array() let nfactor = new Array() // Use map to check if largest common // factor previously present or not let fre = new Map(); // First store m mfactor.push(m); fre[m] = 1; while (m != 1) { // Check whether m is prime or not if (isprm(m)) { mfactor.push(1); fre[1] = 1; m = 1; } // Largest common factor of m else { for (let i = 2; i <= Math.sqrt(m); i++) { // If m is divisible by i if (m % i == 0) { // Store the largest // common factor mfactor.push(m / i); fre[m / i] = 1; m = (m / i); break; } } } } // For number n nfactor.push(n); while (fre[n] != 1) { // Check whether n is prime if (isprm(n)) { nfactor.push(1); n = 1; } // Largest common factor of n else { for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { // Store the largest // common factor nfactor.push(n / i); n = (n / i); break; } } } } // Print the path // Print factors from m for (let i = 0; i < mfactor.length; i++) { // To avoid duplicate printing // of same element if (mfactor[i] == n) break; document.write(mfactor[i] + " <--> "); } // Print the factors from n for (let i = nfactor.length - 1; i >= 0; i--) { if (i == 0) document.write(nfactor[i]); else document.write(nfactor[i] + " <--> "); }}// Driver Code// Given N and Mlet m = 18, n = 19;// Function Callshortestpath(m, n);// This code is contributed by _saurabh_jaiswal |
Output:
18 <--> 9 <--> 3 <--> 1 <--> 19
Time Complexity: O(log (max(M, 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!
