Given an array arr[] of size N where every element is from the range [0, 9]. The task is to reach the last index of the array starting from the first index. From ith index we can move to (i – 1)th, (i + 1)th or to any jth index where j ? i and arr[j] = arr[i].
Examples:
Input: arr[] = {1, 2, 3, 4, 1, 5}
Output: 2
First move from the 0th index to the 4th index
and then from the 4th index to the 5th.Input: arr[] = {1, 2, 3, 4, 5, 1}
Output: 1
Approach: Construct the graph from the given array where the number of nodes in the graph will be equal to the size of the array. Every node of the graph i will be connected to the (i 1)th node, (i + 1)th node and a node j such that i ? j and arr[i] = arr[j]. Now, the answer will be the minimum edges in the path from index 0 to index N – 1 in the constructed graph.
The graph for the array arr[] = {1, 2, 3, 4, 1, 5} is shown in the image below:
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 100005vector<int> gr[N];// Function to add edgevoid add_edge(int u, int v){ gr[u].push_back(v); gr[v].push_back(u);}// Function to return the minimum path// from 0th node to the (n - 1)th nodeint dijkstra(int n){ // To check whether an edge is visited or not // and to keep distance of vertex from 0th index int vis[n] = { 0 }, dist[n]; for (int i = 0; i < n; i++) dist[i] = INT_MAX; // Make 0th index visited and distance is zero vis[0] = 1; dist[0] = 0; // Take a queue and push first element queue<int> q; q.push(0); // Continue this until all vertices are visited while (!q.empty()) { int x = q.front(); // Remove the first element q.pop(); for (int i = 0; i < gr[x].size(); i++) { // Check if a vertex is already visited or not if (vis[gr[x][i]] == 1) continue; // Make vertex visited vis[gr[x][i]] = 1; // Store the number of moves to reach element dist[gr[x][i]] = dist[x] + 1; // Push the current vertex into the queue q.push(gr[x][i]); } } // Return the minimum number of // moves to reach (n - 1)th index return dist[n - 1];}// Function to return the minimum number of moves// required to reach the end of the arrayint Min_Moves(int a[], int n){ // To store the positions of each element vector<int> fre[10]; for (int i = 0; i < n; i++) { if (i != n - 1) add_edge(i, i + 1); fre[a[i]].push_back(i); } // Add edge between same elements for (int i = 0; i < 10; i++) { for (int j = 0; j < fre[i].size(); j++) { for (int k = j + 1; k < fre[i].size(); k++) { if (fre[i][j] + 1 != fre[i][k] and fre[i][j] - 1 != fre[i][k]) { add_edge(fre[i][j], fre[i][k]); } } } } // Return the required minimum number of moves return dijkstra(n);}// Driver codeint main(){ int a[] = { 1, 2, 3, 4, 1, 5 }; int n = sizeof(a) / sizeof(a[0]); cout << Min_Moves(a, n); return 0;} |
Java
// Java implementation of the approachimport java.io.*;import java.util.*;class GFG{ static ArrayList< ArrayList<Integer>> gr = new ArrayList< ArrayList<Integer>>();static int N = 100005;// Function to add edge static void add_edge(int u, int v) { for(int i = 0; i < N; i++) { gr.add(new ArrayList<Integer>()); } gr.get(u).add(v); gr.get(v).add(u);}// Function to return the minimum path // from 0th node to the (n - 1)th node static int dijkstra(int n){ // To check whether an edge is visited // or not and to keep distance of // vertex from 0th index int[] vis = new int[n]; Arrays.fill(vis, 0); int[] dist = new int[n]; for(int i = 0; i < n; i++) { dist[i] = Integer.MAX_VALUE; } // Make 0th index visited and // distance is zero vis[0] = 1; dist[0] = 0; // Take a queue and push first element Queue<Integer> q = new LinkedList<>(); q.add(0); // Continue this until all vertices // are visited while (q.size() > 0) { // Remove the first element int x = q.poll(); for(int i = 0; i < gr.get(x).size(); i++) { // Check if a vertex is already // visited or not if (vis[gr.get(x).get(i)] == 1) { continue; } // Make vertex visited vis[gr.get(x).get(i)] = 1; // Store the number of moves to // reach element dist[gr.get(x).get(i)] = dist[x] + 1; // Push the current vertex into // the queue q.add(gr.get(x).get(i)); } } // Return the minimum number of // moves to reach (n - 1)th index return dist[n - 1];}// Function to return the minimum number of moves // required to reach the end of the array static int Min_Moves(int[] a, int n) { // To store the positions of each element ArrayList< ArrayList<Integer>> fre = new ArrayList< ArrayList<Integer>>(); for(int i = 0; i < 10; i++) { fre.add(new ArrayList<Integer>()); } for(int i = 0; i < n; i++) { if (i != n - 1) { add_edge(i, i + 1); } fre.get(a[i]).add(i); } // Add edge between same elements for(int i = 0; i < 10; i++) { for(int j = 0; j < fre.get(i).size(); j++) { for(int k = j + 1; k < fre.get(i).size(); k++) { if (fre.get(i).get(j) + 1 != fre.get(i).get(k) && fre.get(i).get(j) - 1 != fre.get(i).get(k)) { add_edge(fre.get(i).get(j), fre.get(i).get(k)); } } } } // Return the required minimum // number of moves return dijkstra(n);}// Driver code public static void main(String[] args) { int[] a = { 1, 2, 3, 4, 1, 5 }; int n = a.length; System.out.println(Min_Moves(a, n));}}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation of the approachfrom collections import dequeN = 100005gr = [[] for i in range(N)]# Function to add edgedef add_edge(u, v): gr[u].append(v) gr[v].append(u)# Function to return the minimum path# from 0th node to the (n - 1)th nodedef dijkstra(n): # To check whether an edge is visited # or not and to keep distance of vertex # from 0th index vis = [0 for i in range(n)] dist = [10**9 for i in range(n)] # Make 0th index visited and # distance is zero vis[0] = 1 dist[0] = 0 # Take a queue and # append first element q = deque() q.append(0) # Continue this until # all vertices are visited while (len(q) > 0): x = q.popleft() # Remove the first element for i in gr[x]: # Check if a vertex is # already visited or not if (vis[i] == 1): continue # Make vertex visited vis[i] = 1 # Store the number of moves # to reach element dist[i] = dist[x] + 1 # Push the current vertex # into the queue q.append(i) # Return the minimum number of # moves to reach (n - 1)th index return dist[n - 1]# Function to return the minimum number of moves# required to reach the end of the arraydef Min_Moves(a, n): # To store the positions of each element fre = [[] for i in range(10)] for i in range(n): if (i != n - 1): add_edge(i, i + 1) fre[a[i]].append(i) # Add edge between same elements for i in range(10): for j in range(len(fre[i])): for k in range(j + 1,len(fre[i])): if (fre[i][j] + 1 != fre[i][k] and fre[i][j] - 1 != fre[i][k]): add_edge(fre[i][j], fre[i][k]) # Return the required # minimum number of moves return dijkstra(n)# Driver codea = [1, 2, 3, 4, 1, 5]n = len(a)print(Min_Moves(a, n))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ static List<List<int>> gr = new List<List<int>>(); static int N = 100005; // Function to add edge static void add_edge(int u, int v) { for(int i = 0; i < N; i++) { gr.Add(new List<int>()); } gr[u].Add(v); gr[v].Add(u); } // Function to return the minimum path // from 0th node to the (n - 1)th node static int dijkstra(int n) { // To check whether an edge is visited // or not and to keep distance of // vertex from 0th index int[] vis = new int[n]; Array.Fill(vis, 0); int[] dist = new int[n]; for(int i = 0; i < n; i++) { dist[i] = Int32.MaxValue; } // Make 0th index visited and // distance is zero vis[0] = 1; dist[0] = 0; // Take a queue and push first element Queue<int> q = new Queue<int>(); q.Enqueue(0); // Continue this until all vertices // are visited while(q.Count > 0) { // Remove the first element int x = q.Dequeue(); for(int i = 0; i < gr[x].Count; i++ ) { // Check if a vertex is already // visited or not if(vis[gr[x][i]] == 1) { continue; } // Make vertex visited vis[gr[x][i]] = 1; // Store the number of moves to // reach element dist[gr[x][i]] = dist[x] + 1; // Push the current vertex into // the queue q.Enqueue(gr[x][i]); } } // Return the minimum number of // moves to reach (n - 1)th index return dist[n - 1]; } // Function to return the minimum number of moves // required to reach the end of the array static int Min_Moves(int[] a, int n) { // To store the positions of each element List<List<int>> fre = new List<List<int>>(); for(int i = 0; i < 10; i++) { fre.Add(new List<int>()); } for(int i = 0; i < n; i++) { if (i != n - 1) { add_edge(i, i + 1); } fre[a[i]].Add(i); } // Add edge between same elements for(int i = 0; i < 10; i++) { for(int j = 0; j < fre[i].Count; j++) { for(int k = j + 1; k < fre[i].Count; k++) { if(fre[i][j] + 1 != fre[i][k] && fre[i][j] - 1 != fre[i][k]) { add_edge(fre[i][j], fre[i][k]); } } } } // Return the required minimum // number of moves return dijkstra(n); } // Driver code static public void Main () { int[] a = { 1, 2, 3, 4, 1, 5 }; int n = a.Length; Console.WriteLine(Min_Moves(a, n)); }}// This code is contributed by rag2127 |
Javascript
<script>// Javascript implementation of the approachlet gr = [];let N = 100005;// Function to add edgefunction add_edge(u,v){ for(let i = 0; i < N; i++) { gr.push([]); } gr[u].push(v); gr[v].push(u);}// Function to return the minimum path// from 0th node to the (n - 1)th nodefunction dijkstra(n){ // To check whether an edge is visited // or not and to keep distance of // vertex from 0th index let vis = new Array(n); for(let i = 0; i < vis.length; i++) { vis[i] = 0; } let dist = new Array(n); for(let i = 0; i < n; i++) { dist[i] = Number.MAX_VALUE; } // Make 0th index visited and // distance is zero vis[0] = 1; dist[0] = 0; // Take a queue and push first element let q = []; q.push(0); // Continue this until all vertices // are visited while (q.length > 0) { // Remove the first element let x = q.shift(); for(let i = 0; i < gr[x].length; i++) { // Check if a vertex is already // visited or not if (vis[gr[x][i]] == 1) { continue; } // Make vertex visited vis[gr[x][i]] = 1; // Store the number of moves to // reach element dist[gr[x][i]] = dist[x] + 1; // Push the current vertex into // the queue q.push(gr[x][i]); } } // Return the minimum number of // moves to reach (n - 1)th index return dist[n - 1];}// Function to return the minimum number of moves// required to reach the end of the arrayfunction Min_Moves(a,n){ // To store the positions of each element let fre = []; for(let i = 0; i < 10; i++) { fre.push([]); } for(let i = 0; i < n; i++) { if (i != n - 1) { add_edge(i, i + 1); } fre[a[i]].push(i); } // Add edge between same elements for(let i = 0; i < 10; i++) { for(let j = 0; j < fre[i].length; j++) { for(let k = j + 1; k < fre[i].length; k++) { if (fre[i][j] + 1 != fre[i][k] && fre[i][j] - 1 != fre[i][k]) { add_edge(fre[i][j], fre[i][k]); } } } } // Return the required minimum // number of moves return dijkstra(n);}// Driver codelet a = [1, 2, 3, 4, 1, 5 ];let n = a.length;document.write(Min_Moves(a, n));// This code is contributed by unknown2108</script> |
Output:
2
Time complexity: O(n2)
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!
