Count the number of cyclic elements in an array where we can jump according to the value

Example📎

Input : 

arr[] = {3, 0, 1, 1}

Output: 

1

i.e. Only 1 element is cyclic.

Input : 

arr[] = {3, 0, 1, 1}

Output: 

1

There is only one cyclic point.

The path covered starting from 1 is 1 -> 1

The path covered starting from 2 is 2 -> 3 -> 4 -> 1 -> 1.

The path covered starting from 3 is 3 -> 1 -> 1.

The path covered starting from 4 is 4 -> 2 -> 3 -> 1 -> 1

Input Format: 

You are provided with an integer array.

Output Format: 

You need to return an integer denoting the total number of cyclic elements.

Approach⛏️

To Count the number of cyclic elements in an array where we can jump according to the value, we use kosaraju’s algorithm for finding all strongly connected components.

Algorithm

Algorithm of the function cntCycElements() that is being used to determine the cyclical elements to Count the number of cyclic elements in an array where we can jump according to the value:

/* integer for storing answer */
int count=0;

/* initializing graph data structure */
Graph g(arr.size()+1);
/* for loop for determining whether each element is cyclic or not. */

For i=1 to n:
/* extracting the element from the array */
	ele = arr[i-1];
 
 /* If I + arr[i-1] exceeds the last member, we take mod into account because the array is cyclic.  */
	ver = (x + i) % n + 1;
 
// If there is a self loop, the count of cyclic points is increased.
	if i is equal to ver:
		res++;
 //  creating an edge between i and ver
	g.addEdge(i, ver);
}

res += g.countSCCNodes();

Here's a walkthrough of the algorithm.

Step 1: We are given an array. Our objective is to create a graph.

Step 2: we will start first for the first node, Skipping to the 4th element considering it is in cyclic order. The first element will simply connect to itself. 

Step 3: For the second element, node 2 will first connect to 3 and then to 1. As we know from the previous step, 1 is connected to itself. So, the path ends here.

Step 4: For the third element, node 3 will connect to 1. As we know from the previous step, 1 is connected to itself. So, the path ends here.

Step 5: For the fourth element, node 4 will connect to node 2 then to node 3, and then to node 1. As we know from the previous step, 1 is connected to itself. So, the path ends here.

Implementation in C++

/* C++ Solution of the problem “Count the number of cyclic elements in an array where we can jump according to the value” */

/* Solution of problem “Count the number of cyclic elements in an array where we can jump according to the value” using kosaraju’s algorithm */

#include <bits/stdc++.h>
using namespace std;

class GraphDs {
	int V;
	list<int>* adjList;
	void fillOrder(int v, bool visitedArr[],
	stack<int>& stk);
	int DFSUtil(int v, bool visitedArr[]);

	public:
	GraphDs(int V);
	void addEdge(int v, int w);
	int countSCCNodes();
	GraphDs getTranspose();
};

GraphDs::GraphDs(int V) {
	this->V = V;
	adjList = new list<int>[V];
}

/* Counts number of nodes reachable from v */
int GraphDs::DFSUtil(int v, bool visitedArr[]) {
	visitedArr[v] = true;
	int ans = 1;
	list<int>::iterator i;
	for(i = adjList[v].begin(); i != adjList[v].end(); ++i)
		if (!visitedArr[*i])
			ans += DFSUtil(*i, visitedArr);
	return ans;
}


GraphDs Graph::getTranspose() {
	GraphDs g(V);
	for (int v = 0; v < V; v++) {
		list<int>::iterator i;
		for (i = adjList[v].begin(); i != adjList[v].end(); ++i)
			g.adjList[*i].push_back(v);
	}
	return g;
}

void GraphDs::addEdge(int v, int w) {
	adjList[v].push_back(w);
}

void GraphDs::fillOrder(int v, bool visitedArr[], stack<int>& stk) {
	visitedArr[v] = true;
	list<int>::iterator i;
	for (i = adjList[v].begin(); i != adjList[v].end(); ++i)
	if (!visitedArr[*i])
		fillOrder(*i, visitedArr, stk);
	stk.push(v);
}

/* Using Kosaraju's technique, this function primarily returns the total number of nodes in particular SCCs. */

int GraphDs::countSCCNodes() {
	int res = 0;
	stack<int> stk;
	bool* visitedArr = new bool[V];
	for (int i = 0; i < V; i++)
		visitedArr[i] = false;
		
	for (int i = 0; i < V; i++)
		if (visitedArr[i] == false)
			fillOrder(i, visitedArr, stk);
			
	GraphDs gr = getTranspose();
	
	for (int i = 0; i < V; i++)
		visitedArr[i] = false;
		
	while (stk.empty() == false) {
		int v = stk.top();
		stk.pop();
		if (visitedArr[v] == false) {
			int ans = gr.DFSUtil(v, visitedArr);
			if (ans > 1)
			res += ans;
		}
	}
	
	return res;
}

/* Returns count of cyclic elements in arr[] */
int countCycElement(vector<int>& arr) {
	int ans = 0;
	int n=arr.size();
	// Create a graph of array elements
	GraphDs g(n + 1);

	for (int i = 1; i <= n; i++) {
		int x = arr[i-1];
		/* If I + arr[i-1] exceeds the last member, we take mod into account because the array is cyclic.*/
		int v = (x + i) % n + 1;
		// If there is a self loop, the count of cyclic points is increased.
		if (i == v)
			ans++;
		g.addEdge(i, v);
	}
	
	// Add nodes that have many strongly connected components.
	ans += g.countSCCNodes();
	return ans;
}

int main() {
	vector<int> arr{3, 0, 1, 1};
	cout << countCycElement(arr);
	return 0;
}

Output: 

Time Complexity ⌛

The time complexity of the problem “Count the number of cyclic elements in an array where we can jump according to the value” using the above approach is O(N*N), where N is the number of stations. 

Space Complexity 🚀

The space complexity of the problem “Count the number of cyclic elements in an array where we can jump according to the value” using the above approach is O(N) as we are storing the answer in the custom array.

Frequently Asked Questions ⁉️

What is Graph?

Graphs are non-linear data structures composed of a finite number of nodes or vertices and the edges that connect them.

When would you utilize a graph in a data structure?

Graphs in data structures are used to handle real-world problems by representing the problem area as a network, such as telephone networks, circuit networks, and social networks.

What is a Full Binary Tree?

A full binary tree is a particular kind of binary tree in which every parent node and internal node either has two children or none.

What benefits does binary search offer?

Because the amount of data to be searched is reduced by half with each step in a binary search, one of its key benefits is that it is faster than a serial search.

Where does dynamic programming get used?

Computer networks, routing, graph issues, computer vision, artificial intelligence, machine learning, etc., all use dynamic programming extensively.

Conclusion💡

In this article, we have discussed a coding problem in which we have to Count the number of cyclic elements in an array where we can jump according to the value. We have seen the question's solution, time, and space complexity.

If you think this blog has helped you enhance your knowledge about the above question, and if you want to learn more, check out our articles. 

• Balanced Binary Search Trees 😁
• Binary search tree 😎
• Deletion in Binary Search Tree 🧐
• Unique Binary Search Trees 🤯
   

Recommended problems -

• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k
• Shortest subarray with sum at least k

Visit our website to read more such blogs. Make sure you enroll in the courses we provide, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations.