CODEWITHSUNDEEP
javaalgorithmloopsfor-loopmultidimensional-array
KingHarry
KingHarry

Reputation: 11

Write a program that tests whether there are two 1 lying on the same row or the same column in 2d array

I need to write a program that loops through a 2d array of which the elements consist of either a 1 or 0 and checks if there are two 1's in a row or in a column and then prints true, if I find two 1's on same col or row I can stop there (I don't need to count the 1's).

So I planned on creating a counter for the 1's in the rows and a counter for the 1's in columns and if that counter goes above 1 then the loop breaks and prints. However the counters doesn't reset per row or column, so currently if it finds any two 1's regardless of their position it will print.

I tried adding a rowTotal = 0 & colTotal = 0 at the end of the for loop for each one but doing this then doesn't find any 1's at all.

Also, this is for my data structures & algorithm class so I need to provide a full algorithm, so I don't want to use any functions for this. Any tips on improving my code or a better way to solve this problem would be appreciated. I can do this in either Python or Java.

Many thanks

int[][] board = new int[4][4];



// number to look for
        int findNum = 1;
        // initial total 
        int total = 0;  
        // flag variable to end loop
        boolean found = false;       
        // loops only if found is not 
        for (int i = 0; i < board.length && !found; i++)
        {     
            // resets for each new iteration 
            total = 0;  
            // loops only if found is not 
            for(int j = 0; j < board[i].length && !found; j++)
            {              
                //check row
                if(board[i][j] == findNum) {
                    total++;
                }
                // check column
                if(board[j][i] == findNum) {
                    total++;
                }
                // if more total greater than 1 then end
                if(total > 1) {
                    found = true;
                }
            }

        }

Upvotes: 1

Views: 105

Answers (3)

Tarun Gupta
Tarun Gupta

Reputation: 1669

I think you can iterate through the whole 2d array row wise and check if there are more than one 1's, now transpose the array and repeat the process to check column wise :

 public static void main(String[] args) {

    int[][] board = {   { 0, 0, 0, 0 }, 
                        { 0, 1, 0, 0 }, 
                        { 1, 0, 0, 1 }, 
                        { 0, 0, 1, 0 } };

    if (checkMoreThanOne(board)) {
        System.out.println("Found more than one 1's in rows.");
    }
    int[][] transpose = transpose(board);
    if (checkMoreThanOne(transpose)) {
        System.out.println("Found more than one 1's in columns.");
    }
}

private static boolean checkMoreThanOne(int[][] board) {
    for (int i = 0; i < board.length; i++) {
        int count = 0;
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == 1) {
                if (count > 0)
                    return true;
                else
                    count++;
            }
        }
    }
    return false;
}

private static int[][] transpose(int[][] array) {
    if (array == null || array.length == 0)
        return array;

    int width = array.length;
    int height = array[0].length;

    int[][] array_new = new int[height][width];

    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            array_new[y][x] = array[x][y];
        }
    }
    return array_new;
}

Upvotes: 0

Dave
Dave

Reputation: 9085

Create two sets: one for rows and another for columns.

Loop through the array.

Each time you find a cell with a set bit, check that cell's row and column in your sets. If it exists for either, you're done. If not, update the sets and move on.

Upvotes: 0

Bilal Siddiqui
Bilal Siddiqui

Reputation: 3629

Inside inner loop change if condition to use colTotal instead of rowTotal

 if (colTotal > 1) {
   System.out.println("2 lying on col");
   break;
 }

Remember this break will not break outer loop so you need a flag for eg. 

 boolean found = false; // outside loops

when you print and break just assign true

 found = true; // before break inside inner loop, adjecent to print statement

Now use this flag to check as first statement inside outer loop

 if (found) {
    break;
 }

Or simply you can have it as condition in outer loop 

 for (int i = 0; i < board.length && !found; i++)

Upvotes: 2

Related Questions