-1

Ok so... I need to check if an array is a complete chain. I will show you what this means:

I have arr[5, 3, 2, 0, 4, 1]. N (array size) = 6, N-1 = 5. So array should contain numbers 0-5. THEN we start at arr[0].

arr[0] = 5, so we go to arr[5]= 1, arr[1] = 3, arr[3] = 0, this brings us back to arr[0].

Since this array did not go to EACH number, it is not a complete chain. I hope this makes sense lol.

I am supposed to write a method in java that starts at arr[0] and goes through like I said and if it hits each number in the array it is complete chain (true). If it ever goes back to a number it already hit, it is not (false).

I understand the logic behind this... I just can't implement it. I don't get how to use a loop to keep track of numbers and indices... (we are supposed to use loops).

Could anyone help point me in the right direction? I am not looking for code but if someone could explain how I might implement a loop with this that would be awesome!

6
  • "but if someone could explain how I might implement a loop " -a basic java tutorial perhaps? Nov 10, 2013 at 1:56
  • Have you asked your TA / instructor / professor for assistance?
    – user289086
    Nov 10, 2013 at 1:58
  • Are you asking for pseudo-code that describes this algorithm?
    – wvdz
    Nov 10, 2013 at 1:58
  • Wait.. are you asking for a loop or some method to verify that the members of an array are sequentially valid? Like a way to verify that in an array of ints, that as you progress through the elements of the array that they are incrementing or decrementing in sequence?
    – user562566
    Nov 10, 2013 at 2:53

5 Answers 5

2

I would use an auxiliary boolean[] to tell us if we hit an index a second time. Since you clearly need to have a way to store which elements you have already seen, and since that structure will take linear space in the worst case anyway, you may as well use this. I would do it this way

public static boolean arrayIsCompleteChain(int[] array) {
    boolean[] visited = new boolean[array.length];
    int index = 0;
    int steps = 0;

    // stop once we visit an index twice
    while(!visited[index]) {
        visited[index] = true; // mark index as visited
        index = array[index];  // go to the next index
        steps++;               // count this step
    }

    // if we made one step for every index, then the array is a complete chain
    if(steps == array.length) {
        return true;
    } else {
        return false;
    }

    // for anyone reading this who thinks to himself the "if" construct is
    // unnecessary: this is for didactic purposes
}

Note that this method doesn't do any validation checking on the input, i.e. whether it contains elements that would put the index out of bounds or whether the array itself is null. If you want that, it's fairly easy to do.

0
0

You can use a for loop to iterate in an array. Here is an example:

int[] array = new int[4];
array[0] = 2;
array[1] = 5;
array[2] = 1;
array[3] = 8;

for(int i = 0; i<array.length; i++){
    System.out.println("The element in the array at position: "+ i +" is: " + array[i]);
}

How you can see, I declare and initialize the array first. In the for loop, first I declare and initialize a temp variable (this variable will go to be deleted when the for loop end) to 0 (int i = 0). Next I write the end expression for the "for loop" (i < array.length ), this expression determine when the for will go to finish, in this case the for loop will go to run until "i" be less than the array.length (4). Next I will increase the temp variable by one (i++).

The body of the for loop in this case is simple (print the element of the array in the given position (i)). But it can be whatever you want do with the array.

I hope that you can understand.

PS: Sorry for my English. My first language is Spanish. :D

2
  • java arrays have a length attribute, not method. So you'll actually want to use array.length instead of array.length()
    – Greg Case
    Nov 10, 2013 at 2:50
  • upss! Yes, sorry. Is that the most I use is the List, list.size() :D Nov 10, 2013 at 2:58
0

assuming numbers are unique:

public int sum(int[] arr) {
    int ret = 0;
    for (int i : arr) {
        ret += arr[i];
    }
    return ret;
}

int[] arr = { 5, 3, 2, 0, 4, 1 };
int tmp = arr[0];
int sum = 0;
for (int i = 0; i < arr.length; i++) {
    sum += arr[tmp];
    tmp = arr[tmp];
}
System.out.println(sum == sum(arr));
0

You want to have a counter (initialized to 0) for element that falls out of your chain. You also need a boolean type of array that is the same size of your array. This boolean type of array is to track whether you have duplicate elements.

To make the program faster, in your for-loop (for iterating your array), when you find an element that falls out of your chain range, you increment the counter and break out of the loop. After that you just check whether the counter == 0. If it's 0, then your chain is complete, otherwise incomplete. I hope this helps.

How to check if an element is out the range? check if the element is >= array.length or < 0 (if I understand your problem right)

I realized you may be working on a homework or similar stuff, I leave out most of the code for you to work on it yourself. Below is how I would use a boolean type of array to track element elements:

int[] arrayToCheck = new int[]{5, 3, 2, 0, 1, 1};
boolean[] arrayMarker = new boolean[arrayToCheck.length];

int count = 0;  // count the number out of the chain

for (int i : arrayToCheck) {
    // here you need to write code to check the element i is within
    // your range, if not, increment counter, break out

    if (arrayMarker[i] != true) {
        arrayMarker[i] = true;
    } else {
        count++;
        break;
    }
}

boolean completeChain = (count == 0) ? true : false;
System.out.println("is completeChain: " + completeChain);
-1

I will describe a method that returns the value at a provided index location, given an array of ints.

public static int getAtPosition(int nextPosition, int... elements) {
    return elements[nextPosition];
}

In essence, whatever value I use for nextPosition is used to index into the array.

Consider next, you're seeding your nextPosition by using arr[0] to start, which, if coupled with the method call, results in a next position value of 1.

You also correctly observe that it oscillates, which makes this an invalid chain.

Now, the trick here is selecting a data structure to store the elements we've seen, and to prevent us from triggering duplication once more. Let's use a Set<Integer> to accomplish this, since we can add relatively cheaply, and the interface for Set mandates that it returns true if and only if this element was not added to the set prior.

public static boolean invalidChain(Set<Integer> values, int index) {
    return !values.add(index);
}

An explanation:

  • Given a set of ints, I add the index position that I've just seen.
  • If the index position was successfully added, I return false - because, a successful add() implies that the value was never placed into the set.
  • If the index position was not successfully added, I return true - for the opposite reason for the above.

Given all of this, you now have to author a loop that leverages the boolean invalidChain, and the int getAtPosition. Hint: invalidChain is the only condition you should check within the loop.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.