Check loop in array according to given constraints

Given an array arr[0..n-1] of positive and negative numbers we need to find if there is a cycle in array with given rules of movements. If a number at an i index is positive, then move arr[i]%n forward steps, i.e., next index to visit is (i + arr[i])%n. Conversely, if it’s negative, move backward arr[i]%n steps i.e., next index to visit is (i – arr[i])%n. Here n is size of array. If value of arr[i]%n is zero, then it means no move from index i.

Examples:

Input: arr[] = {2, -1, 1, 2, 2}
Output: Yes
Explanation: There is a loop in this array
because 0 moves to 2, 2 moves to 3, and 3 
moves to 0.

Input  : arr[] = {1, 1, 1, 1, 1, 1}
Output : Yes
Whole array forms a loop.

Input  : arr[] = {1, 2}
Output : No
We move from 0 to index 1. From index
1, there is no move as 2%n is 0. Note that
n is 2.

Code 1:

package com.demo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CheckArrayLoop{

public static void main(String[] args) {

int mm[]={ 4, 3, 2, 1,2 };
for(int i=0;i<mm.length;i++){
System.out.print(mm[i]+"->");

}
cycleOfArray(mm);

}

// Function to find all permuted rows of a given row r
public static void cycleOfArray(int mat[]) {
Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < mat.length; i++) {
if (map.size() > 0 && map.containsKey(String.valueOf(mat[i]))) {
map.put(String.valueOf(mat[i]),
map.get(String.valueOf(mat[i])) + 1);
} else {
map.put(String.valueOf(mat[i]), 1);
}
}
System.out.println();
boolean flag = false;
for (int i = 0; i < mat.length; i++) {
if (map.size() > 0 && map.containsKey(String.valueOf(mat[i]))
&& map.get(String.valueOf(mat[i])) > 1) {
System.out.println("Circular connection" + mat[i]);
flag = true;
}
if (i == mat.length && !flag) {
System.out.println("No search circule");
}
}

}

}

Output:

4->3->2->1->2->
Circular connection2
Circular connection2

About Kartik Chandra Mandal

I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.