Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Approach
5.
Algorithm
6.
Complexity
7.
Implementation in C++
8.
Implementation in Java
9.
Implementation in Python
10.
Frequently Asked Questions
10.1.
What is the use of the memset() method in C++?
10.2.
What is the time complexity of counting the number of magical Indices in an array problem?
10.3.
What is the space complexity of counting the number of magical Indices in an array problem?
11.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count the number of magical Indices in an array

Author Nagendra
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

magical indices image

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. 

Example

Input : Array = {1, 1, 1, 1}
Output: 4
Possible traversals:

1 -> 3 -> 1
2 -> 4 -> 2
3 -> 1 -> 3
4 -> 2 -> 4
You can also try this code with Online C++ Compiler
Run Code

Magical indices = 1, 2, 3, 4

 

Input: Array = {0, 0, 0, 2}
Output: 2
Possible traversals:

1 -> 2 -> 3 -> 4 -> 3...
2 -> 3 -> 4 -> 3...
3 -> 4 -> 3
4 -> 3 ->4
You can also try this code with Online C++ Compiler
Run Code

Magical indices = 3, 4

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
Run Code

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;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

4
You can also try this code with Online Java Compiler
Run Code

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));
    }
}
You can also try this code with Online Java Compiler
Run Code


Output:

4
You can also try this code with Online Python Compiler
Run Code

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))
You can also try this code with Online Python Compiler
Run Code

 

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.

 

Recommended problems -

 

We hope that this blog has helped you enhance your knowledge regarding Count the number of magical Indices in an array, and if you would like to learn more, you can refer to our guided paths on the Coding Ninjas Studio platform to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. To practice and improve yourself in the interview, you can also check out Top 100 SQL problemsInterview experienceCoding interview questions, and the Ultimate guide path for interviews. Do upvote our blog to help other ninjas grow. Happy Coding!!

Thank you image
Live masterclass