Contents
Path through graph Codevita 9 Solution
You are given two natural numbers. Imagine these natural numbers as nodes on a graph. On this graph, a number is connected to its largest factor other than itself. You have to find the shortest path between them and print the number of edges on that path.
If the two numbers do not have any common factor, then construct a path through 1. For better understanding refer to the examples below:
Example 1:
Input numbers: 2 4
The numbers are directly connected as follows on the graph. 2 is the largest factor of 4, other than itself.
We can also see that there is only on edge between them.
4 <–> 2
Hence the number of edges in shortest path is 1.
Output: 1
Example 2:
Input numbers: 18 19
The graph for number 18 and 19 will look like this. Here we have 4 edges in the path.
18 <–> 9 <–> 3 <–> 1 <–> 19Output: 4
Example 3:
Input numbers: 9 9
The number of edges in shortest path is zero since the numbers correspond to the same node.
Output: 0
Constraints
0 < M, N <= 10 ^ 9
Input
Single line containing two space separated integers M, N
Output
Number of edges in the shortest path.
Time Limit
Examples
Example 1
Output
5
Explanation :
The graph for number 15689 and 28 will look like this.
Since we know that largest factor of 15689 other than itself is 541.
Since 541 is a prime number, it’s largest factor other than itself is 1.
For number 28, it’s largest factor other than itself is 14.
Largest factor of 14, other than itself is 7.
Since 7 is a prime number, it’s largest factor other than itself is 1.
So, the graph will look like this:
15689 <–> 541 <–> 1 <–> 7 <–> 14 <–> 28
Since there are 5 edges in this graph, output will be 5.
Example 2
Input
16 4
Output
2
Explanation :
The graph for number 16 and 4 will look like this.
Since we know that largest factor of 16 other than itself is 8.
Largest factor of 8 other than itself is 4. That’s the other input number, so we will stop here.
So, the graph will look like this:
16<–>8<–>4
Since there are 2 edges in this graph, output will be 2.
SOLUTION
Program: Path through graph Codevita 9 Solution in C++
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' int get(int x) { for (int i = 2; i * i <= x; i++) { if (x % i == 0) return x / i; } return 1; } void sol() { int x, y; cin >> x >> y; if (x < y) swap(x, y); if (x == y) { cout << 0; return; } map<int, int> m; int c = 0; while (x != 1) { c++; x = get(x); m[x] = c; } c = 0; while (!m.count(y)) { c++; y = get(y); } cout << c + m[y]; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); sol(); return 0; }
Codevita Season 9 All Questions Solution
- Even Odd Codevita 9 Solution
- Largest Gold Ingot Codevita 9 Solution
- Fill the Cube Codevita 9 Solution
- Logic for Single Lane Highway Codevita 9
- Faulty Keyboard Codevita 9 Solution 2020
- Signal Connection Codevita 9 Solution 2020
- Closing Value Codevita 9 Solution
- CodeVita season 9 Zone 2 All Solutions
- Railway Station Codevita 9 Solution
- Count Pairs Codevita 9 Solution
- 7 X 7 Codevita 9 Solution
- Tennis Score codevita 9 Solution
- Unlocker Codevita 9 Solution
- Path through graph Codevita 9 Solution
- Secret Word Codevita 9 Solution
- 3 Palindrome Codevita 9 Solution
- Max Sum Codevita 9 Solution
- Equalize Weights Codevita 9 Solution
- Binary Equivalent Codevita 9 Solution
- String Word Codevita 9 Solution
- 4 Particles Codevita 9 Solution
- String Pair Codevita 9 Solution
- Corona Virus Codevita 9 Solutions
- Factor of 3 Codevita 9 Solutions
- Single Lane Highway Codevita 9 Solution