Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Data structures are pre-programmed structures that are used to store ordered data to make various actions on it simple. It stands for the knowledge of how data should be stored in memory. It should be created and put into use in a way that makes things simpler and more effective.
This article explains the detailed solution of the problem: Count the number of magical indices in an array along with its implementation in different programming languages.
Without further ado, let's get started.
Problem Statement
Suppose there is an integer array A. If j = (i + A[i])% n + 1, then index i of A is said to be connected to index j. (Assume 1-based indexing). Index i is a magical index if it is visited more than once when traversing the array in the order given. Count how many magical indexes there are in the array.
Let's look at the approach for solving the problem.
Approach
The problem statement is counting the number of nodes in each cycle that exists in the graph. Each index corresponds to a single graph node. According to the problem statement definition, each node has a single directed edge. A cycle is always observed when traversing this graph, which has a unique attribute. This characteristic will aid in lowering the solution's time complexity.
Let node i be where the traversal starts. This traversal's parent node, designated as node i will be responsible for all of the nodes visited during the traversal. A new cycle is recognised if, when traversing the graph, we come across a node that has already been visited and whose parent node coincides with the parent node of the traverse. Start a new dfs from this node and keep going till the same node isn't visited any more to count the number of nodes in this cycle. This process is carried out again for each node I in the graph. In the worst case, each node will only be visited three times. Therefore, the solution's temporal complexity is linear.
Let's look at the algorithm for the approach.
Algorithm
The algorithm for Count the number of magical Indices in an array:
1. For each node in the graph:
if node i is not visited then:
for every adjacent node j:
if node j is not visited:
Array[j] = i
else:
if Array[j]==i
cycle detected
count nodes in cycle
2. return count
You can also try this code with Online C++ Compiler
The Time Complexity of the approach is O(n). The Space Complexity of the approach is O(n).
Let's look at the implementation in different languages.
Implementation in C++
Code:
#include <bits/stdc++.h>
using namespace std;
int magicalIndices(int A[], int n)
{
int i, ctr = 0, j;
// Array to store parent node of traversal.
int parent[n + 1];
//Array to count the visited
int visited[n + 1];
// Initializing the arrays.
memset(parent, -1, sizeof(parent));
memset(visited, 0, sizeof(visited));
for (i = 0; i < n; i++) {
j = i;
//Verify whether the current node has been explored previously. If node has not yet been traversed, parent value will be -1.
if (parent[j] == -1) {
//Traversing the Graph
while (parent[j] == -1) {
parent[j] = i;
j = (j + A[j] + 1) % n;
}
if (parent[j] == i) {
while (!visited[j]) {
visited[j] = 1;
ctr++; //Counting the number of nodes.
j = (j + A[j] + 1) % n;
}
}
}
}
return ctr;
}
int main()
{
int arr[] = { 1, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << magicalIndices(arr, n);
return 0;
}
You can also try this code with Online C++ Compiler
import java.io.*;
import java.util.*;
public class ninja2 {
static int magicalIndices(int []A, int n)
{
int i, ctr = 0, j;
// Array to store parent node of traversal.
int []parent = new int[n + 1];
//Array to count the visited
int []visited= new int[n + 1];
// Initializing the arrays.
for (i = 0; i < n+1; i++) {
parent[i] = -1;
visited[i] = 0;
}
for (i = 0; i < n; i++) {
j = i;
//Verify whether the current node has been explored previously. If node has not yet been traversed, parent value will be -1.
if (parent[j] == -1) {
//Traversing the Graph
while (parent[j] == -1) {
parent[j] = i;
j = (j + A[j] + 1) % n;
}
if (parent[j] == i) {
while (visited[j]==0) {
visited[j] = 1;
ctr++; //Counting the number of nodes.
j = (j + A[j] + 1) % n;
}
}
}
}
return ctr;
}
public static void main(String args[])
{
int[] arr = { 1,1,1,1};
int n = arr.length;
System.out.print(magicalIndices(arr, n));
}
}
You can also try this code with Online Java Compiler
def magicalIndices(A, n) :
ctr = 0
#List to store parent node of traversal.
parent = [None] * (n + 1)
#List to count the visited
visited = [None] * (n + 1)
# Initializing the lists.
for i in range(0, n+1):
parent[i] = -1
visited[i] = 0
for i in range(0, n):
j = i
#Verify whether the current node has been explored previously. If node has not yet been traversed, parent value will be -1.
if (parent[j] == -1) :
#Traversing the Graph.
while (parent[j] == -1) :
parent[j] = i
j = (j + A[j] + 1) % n
if (parent[j] == i) :
while (visited[j]==0) :
visited[j] = 1
ctr = ctr + 1 #Counting the number of nodes.
j = (j + A[j] + 1) % n
return ctr
# Driver code
l = [1,1,1,1 ]
n = len(l)
print (magicalIndices(l, n))
You can also try this code with Online Python Compiler