CODEWITHSUNDEEP
arraysalgorithmiterationpermutation
Zeus
Zeus

Reputation: 2253

Moving along a 1D Array

I came across this question in an online coding challenge recently, but I can't seem to make any head way.

There's a 1D array consisting of 0 and 1.

A player starts at index 0 and needs to go beyond the length of the array.

Once the length of the array is crossed the player wins.

The player can only go into indices that have a 0.

A player can move 1 step back, 1 step forward or m steps forward.

The question is how to find out if a game is winnable.

It all boils down to the following function signature:

boolean winnable(int[] arr, int m){
}

Can someone help me with an algorithm to get started.

Added Later

I can up with this algorithm, which of course doesn't pass most of the test cases.

public static boolean winnable(int[] arr, int m){
        int currPos = 0;
        for(int i=1; i< arr.length; i++){
            if(currPos == arr.length -1 - m) return true;
            else if(arr[i] == 0)currPos++;
            else if(arr[i] == 1){
                if(arr[currPos + m] == 0) currPos = currPos + m;
            }
        }
        return false;
    }

Upvotes: 0

Views: 175

Answers (4)

K. M. Fazle Azim Babu
K. M. Fazle Azim Babu

Reputation: 195

It can be solved cleanly using BFS. Here goes my solution:

private static boolean isReachable(int[] array, int m) {
    boolean[] visited = new boolean[array.length];
    Queue<Integer> queue = new LinkedList<>();

    queue.add(0);
    visited[0] = true;
    while (!queue.isEmpty()) {
        Integer current = queue.poll();
        if (current+m >= array.length) {
            return true;
        } else if (current+m < array.length && array[current+m] == 0 && !visited[current+m]) {
            queue.add(current+m);
            visited[current+m] = true;
        }

        if (current+1 >= array.length) {
            return true;
        } else if (current+1 < array.length && array[current+1] == 0 && !visited[current+1]) {
            queue.add(current+1);
            visited[current+1] = true;
        }

        if (current-1 >= 0 && array[current-1] == 0 && !visited[current-1]) {
            queue.add(current-1);
            visited[current-1] = true;
        }
    }
    return false;
}

Upvotes: 0

Debosmit Ray
Debosmit Ray

Reputation: 5403

I just added an accepted solution to this problem on HackerRank.

This is a recursive approach. I created a helper function that would take the currentIndx, array, jumpValue and a Set of visited indices as arguments.

Since currentIndx can't be < 0, I return false; If currentIndx > arr.length - 1, we are done. If the value at currentIndx is not 0, we again have to return false since it cannot be in the path.

Now, after these checks we add the visited index to the set. If the add operation returns false, that index must have been visited previously; so we return false.

Then, we recurse. We call the same function with currentIndx - 1, currentIndx + 1 and currentIndx + jumpValue to see what it returns. If any of these are true, we have found a path.

[Java source code]

Upvotes: 0

user3386109
user3386109

Reputation: 34829

You're going to need a queue, or some other way to remember what indexes need to be checked. Each time you reach a zero that hasn't been seen before, you need to check 3 indexes: the one before, the one after, and the one at distance m.

The size of the queue is limited to the number of zeros in the input array. For example, if the input array has 10 zeros, then the queue can't possibly have more than 10 items in it. So you could implement the queue as a simple array that's the same size as the input array.

Here's some pseudo-code that shows how to solve the problem:

writeToQueue(0)
while ( queue is not empty )
{
    index = readFromQueue
    if ( index >= length-m )
        the game is winnable

    array[index] = 1  // mark this index as visited

    if ( index > 0 && array[index-1] == 0 )    // 1 step back
        writeToQueue(index-1)
    if ( array[index+1] == 0 )    // 1 step forward
        writeToQueue(index+1)
    if ( array[index+m] == 0 )    // m steps forward
        writeToQueue(index+m)
}
if the queue empties without reaching the end, the game is not winnable

Note that the input array is used to keep track of which indexes have been visited, i.e. each 0 that is found is changed to a 1, until either the game is won, or no more 0's are reachable.

Upvotes: 1

matanso
matanso

Reputation: 1292

Iterate over the entire array. For each cell -> If it is 1, mark it as unreachable. Else, check if it is reachable. A cell is reachable if either A) the cell before it is reachable B) the cell m cells before it is reachable.

Once a cell is marked as reachable, you must also mark all consecutive cells behind it which are all '0' as reachable. Once you have marked a cell less than m cells from the end as reachable, that means the end is reachable. If you've marked the last m cells as unreachable, the end is unreachable.

Upvotes: 2

Related Questions