Count of elements which form a loop in an Array according to given constraints | Java program to number of elements which form a cycle in an array ; Function to count number of elements forming a cycle ; Array to store parent node of traversal . ; Array to determine whether current node is already counted in the cycle . ; Initialize the arrays . ; Check if current node is already traversed or not . If node is not traversed yet then parent value will be - 1. ; Traverse the graph until an already visited node is not found . ; Check parent value to ensure a cycle is present . ; Count number of nodes in the cycle . ; Driver code
import java . util . * ; class GFG { static final int mod = 1000000007 ; static int solve ( int A [ ] , int n ) { int i , cnt = 0 , j ; int [ ] parent = new int [ n ] ; int [ ] vis = new int [ n ] ; Arrays . fill ( parent , - 1 ) ; Arrays . fill ( vis , 0 ) ; for ( i = 0 ; i < n ; i ++ ) { j = i ; if ( parent [ j ] == - 1 ) { while ( parent [ j ] == - 1 ) { parent [ j ] = i ; j = __gcd ( j , A [ j ] ) % n ; } if ( parent [ j ] == i ) { while ( vis [ j ] == 0 ) { vis [ j ] = 1 ; cnt ++ ; j = __gcd ( j , A [ j ] ) % n ; } } } } return cnt ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } public static void main ( String [ ] args ) { int A [ ] = { 1 , 1 , 6 , 2 } ; int n = A . length ; System . out . print ( solve ( A , n ) ) ; } }