CODEWITHSUNDEEP
java
dollaza
dollaza

Reputation: 213

brute force solution for celebrity algorithm in java

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.

I'm aware that this can be solved using a queue or a stack but I'd like to first solve it using brute force to practice working my way up. My attempt loops through a matrix to see which row has all 0s. Now how do I double check if that row contains one 0 and the rest 1s? Here is my code:

public static int[][] matrix = {{0, 0, 1, 0},
                                {0, 0, 1, 0},
                                {0, 0, 0, 0},
                                {0, 0, 1, 0}};

public static void main(String[] args) {
    if(knowsCeleb() > 0){
        System.out.println(knowsCeleb() + " is the celebrity.");
    }else{
        System.out.println("There is no celebrity.");
    }
}

public static int knowsCeleb(){
    int count = 0;

    for(int i = 0; i < matrix.length; i++){
        for(int j = 0; j < matrix[i].length; j++){

            if(matrix[i][j] == 0){
                count++;
            }else{
                count = 0;
                break;
            }
        }

        if(count == matrix[i].length){
            return (i+1);
        }
    }
    return 0;
}

In this case, the third row is the celebrity because it knows no one (0s in the row) but every one knows it (1s in the column). How do I fix my code so it double checks that the correct column contains 1s and one zero. For example, this input:

 public static int[][] matrix = {{0, 0, 1, 0},
                                {0, 0, 1, 0},
                                {0, 0, 1, 0},
                                {0, 0, 0, 0}};

prints that the 4 is a celebrity even though no one knows 4 (no 1s in the last column). How do I execute the second check to verify it is in fact a celebrity? Please help!

Upvotes: 0

Views: 418

Answers (1)

chickity china chinese chicken
chickity china chinese chicken

Reputation: 8047

If I understand the goal correctly, it seems you have already described the condition that must be met to confirm the matrix entry: "double check that the correct column contains 1s and one zero." So we could make a method that does just that, explicitly check the the column contains ones and one zero:

public static boolean confirm(int column){
    int zeros = 0;
    int ones = 0;
    column = column - 1; // java indexes from zero, so we decrement column

    boolean confirmed = false; // set the result initially unconfirmed

    // for each row
    for(int i = 0; i < matrix[column].length; i++){
        // if the value in the specified column is zero
        if (matrix[i][column] == 0)
            // add to zeros
            zeros++;
        // otherwise if the value in the specified column is one
        else if (matrix[i][column] == 1)
            // add to ones
            ones++;
    }

    // the condition we want to double check 
    // "correct column contains 1s and one zero"
    if (zeros == 1 && ones == 3){
        confirmed = true;  // confirm
    }
    return confirmed; 
}

Now that we've got the method available, call it from main: 

System.out.println("Confirm " + knowsCeleb() + ": " + confirm(knowsCeleb()));

Gives output something like:

3 is the celebrity.
Confirm 3: true

Upvotes: 1

Related Questions