Given an array of integers and a number K with initial and final values. Your task is to find the minimum number of steps required to get final value starting from the initial value using the array elements. You can only do add (add operation % 1000) on values to get the final value. At every step, you are allowed to add any of the array elements with modulus operation.
Examples:
Input: initial = 1, final = 6, a[] = {1, 2, 3, 4}
Output: 2
Step 1: (1 + 1 ) % 1000 = 2.
Step 2: (2 + 4) % 1000 = 6 (which is required final value).Input: start = 998 end = 2 a[] = {2, 1, 3}
Output: 2
Step 1 : (998 + 2) % 1000 = 0.
Step 2 : (0 + 2) % 1000 = 2.
OR
Step 1 : (998 + 1) % 1000 = 999.
Step 2 : (999 + 3) % 1000 = 2
Approach:
Since in the above problem the modulus given is 1000, therefore the maximum number of states will be 103. All the states can be checked using simple BFS. Initialize an ans[] array with -1 which marks that the state has not been visited. ans[i] stores the number of steps taken to reach i from start. Initially push the start to the queue, then apply BFS.
Pop the top element and check if it is equal to the end if it is then print the ans[end]. If the element is not equal to the topmost element, then add the top element with every element in the array and perform a mod operation with 1000. If the added element state has not been visited previously, then push it into the queue. Initialize ans[pushed_element] by ans[top_element] + 1.
Once all the states are visited, and the state cannot be reached by performing every possible multiplication, then print -1.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum steps// to reach end from start by performing// additions and mod operations with array elements#include <bits/stdc++.h>using namespace std;// Function that returns the minimum operationsint minimumAdditions(int start, int end, int a[], int n){ // array which stores the minimum steps // to reach i from start int ans[1001]; // -1 indicated the state has not been visited memset(ans, -1, sizeof(ans)); int mod = 1000; // queue to store all possible states queue<int> q; // initially push the start q.push(start % mod); // to reach start we require 0 steps ans[start] = 0; // till all states are visited while (!q.empty()) { // get the topmost element in the queue int top = q.front(); // pop the topmost element q.pop(); // if the topmost element is end if (top == end) return ans[end]; // perform addition with all array elements for (int i = 0; i < n; i++) { int pushed = top + a[i]; pushed = pushed % mod; // if not visited, then push it to queue if (ans[pushed] == -1) { ans[pushed] = ans[top] + 1; q.push(pushed); } } } return -1;}// Driver Codeint main(){ int start = 998, end = 2; int a[] = { 2, 1, 3 }; int n = sizeof(a) / sizeof(a[0]); // Calling function cout << minimumAdditions(start, end, a, n); return 0;} |
Java
// Java program to find the minimum steps// to reach end from start by performing// additions and mod operations with array elementsimport java.util.*;class GFG{ // Function that returns // the minimum operations static int minimumAdditions(int start, int end, int a[], int n) { // array which stores the minimum steps // to reach i from start int ans[] = new int[1001]; // -1 indicated the state has not been visited Arrays.fill(ans, -1); int mod = 1000; // queue to store all possible states Queue<Integer> q = new java.util.LinkedList<>(); // initially push the start q.add(start % mod); // to reach start we require 0 steps ans[start] = 0; // till all states are visited while (!q.isEmpty()) { // get the topmost element in the queue int top = q.peek(); // pop the topmost element q.poll(); // if the topmost element is end if (top == end) { return ans[end]; } // perform addition with all array elements for (int i = 0; i < n; i++) { int pushed = top + a[i]; pushed = pushed % mod; // if not visited, then push it to queue if (ans[pushed] == -1) { ans[pushed] = ans[top] + 1; q.add(pushed); } } } return -1; } // Driver Code public static void main(String[] args) { int start = 998, end = 2; int a[] = {2, 1, 3}; int n = a.length; // Calling function System.out.println(minimumAdditions(start, end, a, n)); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 program to find the minimum steps# to reach end from start by performing# additions and mod operations with array# elementsfrom collections import dequefrom typing import List# Function that returns the minimum operationsdef minimumAdditions(start: int, end: int, a: List[int], n: int) -> int: # Array which stores the minimum steps # to reach i from start # -1 indicated the state has not been visited ans = [-1] * 1001 mod = 1000 # Queue to store all possible states q = deque() # Initially push the start q.append(start % mod) # To reach start we require 0 steps ans[start] = 0 # Till all states are visited while q: # Get the topmost element in the queue top = q[0] # Pop the topmost element q.popleft() # If the topmost element is end if (top == end): return ans[end] # Perform addition with all array elements for i in range(n): pushed = top + a[i] pushed = pushed % mod # If not visited, then push it to queue if (ans[pushed] == -1): ans[pushed] = ans[top] + 1 q.append(pushed) return -1# Driver Codeif __name__ == "__main__": start = 998 end = 2 a = [ 2, 1, 3 ] n = len(a) # Calling function print(minimumAdditions(start, end, a, n))# This code is contributed by sanjeev2552 |
C#
// C# program to find the minimum steps// to reach end from start by performing// additions and mod operations with array elementsusing System;using System.Collections.Generic; class GFG{ // Function that returns // the minimum operations static int minimumAdditions(int start, int end, int []a, int n) { // array which stores the minimum steps // to reach i from start int []ans = new int[1001]; // -1 indicated the state has not been visited for(int i = 0; i < 1001; i++) { ans[i] = -1; } int mod = 1000; // queue to store all possible states Queue<int> q = new Queue<int>(); // initially push the start q.Enqueue(start % mod); // to reach start we require 0 steps ans[start] = 0; // till all states are visited while (q.Count != 0) { // get the topmost element in the queue int top = q.Peek(); // pop the topmost element q.Dequeue(); // if the topmost element is end if (top == end) { return ans[end]; } // perform addition with all array elements for (int i = 0; i < n; i++) { int pushed = top + a[i]; pushed = pushed % mod; // if not visited, then push it to queue if (ans[pushed] == -1) { ans[pushed] = ans[top] + 1; q.Enqueue(pushed); } } } return -1; } // Driver Code public static void Main(String[] args) { int start = 998, end = 2; int []a = {2, 1, 3}; int n = a.Length; // Calling function Console.WriteLine(minimumAdditions(start, end, a, n)); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find the minimum steps// to reach end from start by performing// additions and mod operations with array elements// Function that returns // the minimum operationsfunction minimumAdditions(start,end,a,n){ // array which stores the minimum steps // to reach i from start let ans = new Array(1001); // -1 indicated the state has not been visited for(let i=0;i<1001;i++) ans[i]=-1; let mod = 1000; // queue to store all possible states let q = []; // initially push the start q.push(start % mod); // to reach start we require 0 steps ans[start] = 0; // till all states are visited while (q.length!=0) { // get the topmost element in the queue let top = q[0]; // pop the topmost element q.shift(); // if the topmost element is end if (top == end) { return ans[end]; } // perform addition with all array elements for (let i = 0; i < n; i++) { let pushed = top + a[i]; pushed = pushed % mod; // if not visited, then push it to queue if (ans[pushed] == -1) { ans[pushed] = ans[top] + 1; q.push(pushed); } } } return -1;}// Driver Codelet start = 998, end = 2;let a=[2, 1, 3];let n = a.length; // Calling functiondocument.write(minimumAdditions(start, end, a, n));// This code is contributed by rag2127</script> |
Output
2
Time Complexity: 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!
