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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

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

Complexity

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;
}

Output:

4

Implementation in Java

Code:

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));
}
}

Output:

4

Implementation in Python

Code:

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))

Output:

4

Frequently Asked Questions

What is the use of the memset() method in C++?

Using memset() method, a block of memory can be filled with a specific value.

What is the time complexity of counting the number of magical Indices in an array problem?

The Time Complexity of the approach discussed in the article is O(n).

What is the space complexity of counting the number of magical Indices in an array problem?

The Space Complexity of the approach discussed in the article is O(n).

Conclusion

In this article, we have extensively discussed the detailed solution of the problem: Count the number of magical Indices in an array.