Якщо задано позитивне число N, нам потрібно досягти 1 за мінімальну кількість кроків, де крок визначається як перетворення N на (N-1) або перетворення N на один із більших дільників.
Формально, якщо ми знаходимося на N, то за 1 крок ми можемо досягти (N - 1), або якщо N = u*v, тоді ми можемо досягти max(u v), де u > 1 і v > 1.
приклади:
мій живий цвіркун
Input : N = 17 Output : 4 We can reach to 1 in 4 steps as shown below 17 -> 16(from 17 - 1) -> 4(from 4 * 4) -> 2(from 2 * 2) -> 1(from 2 - 1) Input : N = 50 Output : 5 We can reach to 1 in 5 steps as shown below 50 -> 10(from 5 * 10) -> 5(from 2 * 5) -> 4(from 5 - 1) -> 2(from 2 *2) -> 1(from 2 - 1)
Ми можемо вирішити цю проблему за допомогою пошуку в ширину, оскільки він працює рівень за рівнем, тому ми досягнемо 1 за мінімальну кількість кроків, де наступний рівень для N містить (N - 1) і більші належні множники N.
Повна процедура BFS буде такою. Спочатку ми вставимо N із кроком 0 у чергу даних, а потім на кожному рівні ми вставимо їхні елементи наступного рівня на 1 крок більше, ніж елементи попереднього рівня. Таким чином, коли 1 буде винесено з черги, він міститиме мінімальну кількість кроків, що буде нашим кінцевим результатом.
У наведеному нижче коді використовується черга зі структурою типу «дані», яка зберігає значення та кроки від N, у ній використовується інший набір цілочисельного типу, щоб уберегти нас від проштовхування того самого елемента більше одного разу, що може призвести до нескінченного циклу. Тож на кожному кроці ми вставляємо значення в набір після того, як вставляємо його в чергу, щоб значення не відвідувалося більше одного разу.
Перегляньте код нижче для кращого розуміння
C++// C++ program to get minimum step to reach 1 // under given constraints #include
// Java program to get minimum step to reach 1 // under given constraints import java.util.*; class GFG { // structure represent one node in queue static class data { int val; int steps; public data(int val int steps) { this.val = val; this.steps = steps; } }; // method returns minimum step to reach one static int minStepToReachOne(int N) { Queue<data> q = new LinkedList<>(); q.add(new data(N 0)); // set is used to visit numbers so that they // won't be pushed in queue again HashSet<Integer> st = new HashSet<Integer>(); // loop until we reach to 1 while (!q.isEmpty()) { data t = q.peek(); q.remove(); // if current data value is 1 return its // steps from N if (t.val == 1) return t.steps; // check curr - 1 only if it not visited yet if (!st.contains(t.val - 1)) { q.add(new data(t.val - 1 t.steps + 1)); st.add(t.val - 1); } // loop from 2 to Math.sqrt(value) for its divisors for (int i = 2; i*i <= t.val; i++) { // check divisor only if it is not visited yet // if i is divisor of val then val / i will // be its bigger divisor if (t.val % i == 0 && !st.contains(t.val / i) ) { q.add(new data(t.val / i t.steps + 1)); st.add(t.val / i); } } } return -1; } // Driver code public static void main(String[] args) { int N = 17; System.out.print(minStepToReachOne(N) +'n'); } } // This code is contributed by 29AjayKumar
# Python3 program to get minimum step # to reach 1 under given constraints # Structure represent one node in queue class data: def __init__(self val steps): self.val = val self.steps = steps # Method returns minimum step to reach one def minStepToReachOne(N): q = [] q.append(data(N 0)) # Set is used to visit numbers # so that they won't be pushed # in queue again st = set() # Loop until we reach to 1 while (len(q)): t = q.pop(0) # If current data value is 1 # return its steps from N if (t.val == 1): return t.steps # Check curr - 1 only if # it not visited yet if not (t.val - 1) in st: q.append(data(t.val - 1 t.steps + 1)) st.add(t.val - 1) # Loop from 2 to Math.sqrt(value) # for its divisors for i in range(2 int((t.val) ** 0.5) + 1): # Check divisor only if it is not # visited yet if i is divisor of val # then val / i will be its bigger divisor if (t.val % i == 0 and (t.val / i) not in st): q.append(data(t.val / i t.steps + 1)) st.add(t.val / i) return -1 # Driver code N = 17 print(minStepToReachOne(N)) # This code is contributed by phasing17
// C# program to get minimum step to reach 1 // under given constraints using System; using System.Collections.Generic; class GFG { // structure represent one node in queue class data { public int val; public int steps; public data(int val int steps) { this.val = val; this.steps = steps; } }; // method returns minimum step to reach one static int minStepToReachOne(int N) { Queue<data> q = new Queue<data>(); q.Enqueue(new data(N 0)); // set is used to visit numbers so that they // won't be pushed in queue again HashSet<int> st = new HashSet<int>(); // loop until we reach to 1 while (q.Count != 0) { data t = q.Peek(); q.Dequeue(); // if current data value is 1 return its // steps from N if (t.val == 1) return t.steps; // check curr - 1 only if it not visited yet if (!st.Contains(t.val - 1)) { q.Enqueue(new data(t.val - 1 t.steps + 1)); st.Add(t.val - 1); } // loop from 2 to Math.Sqrt(value) for its divisors for (int i = 2; i*i <= t.val; i++) { // check divisor only if it is not visited yet // if i is divisor of val then val / i will // be its bigger divisor if (t.val % i == 0 && !st.Contains(t.val / i) ) { q.Enqueue(new data(t.val / i t.steps + 1)); st.Add(t.val / i); } } } return -1; } // Driver code public static void Main(String[] args) { int N = 17; Console.Write(minStepToReachOne(N) +'n'); } } // This code is contributed by 29AjayKumar
<script> // Javascript program to get minimum step // to reach 1 under given constraints // Structure represent one node in queue class data { constructor(val steps) { this.val = val; this.steps = steps; } } // Method returns minimum step to reach one function minStepToReachOne(N) { let q = []; q.push(new data(N 0)); // Set is used to visit numbers // so that they won't be pushed // in queue again let st = new Set(); // Loop until we reach to 1 while (q.length != 0) { let t = q.shift(); // If current data value is 1 // return its steps from N if (t.val == 1) return t.steps; // Check curr - 1 only if // it not visited yet if (!st.has(t.val - 1)) { q.push(new data(t.val - 1 t.steps + 1)); st.add(t.val - 1); } // Loop from 2 to Math.sqrt(value) // for its divisors for(let i = 2; i*i <= t.val; i++) { // Check divisor only if it is not // visited yet if i is divisor of val // then val / i will be its bigger divisor if (t.val % i == 0 && !st.has(t.val / i)) { q.push(new data(t.val / i t.steps + 1)); st.add(t.val / i); } } } return -1; } // Driver code let N = 17; document.write(minStepToReachOne(N) + '
'); // This code is contributed by rag2127 </script>
Вихід:
4