How do you determine if the number exists in the matrix in O(N) run time or bett

Question

How do you determine if the number exists in the matrix in O(N) run time or better? Below is my working code.

import java.util.Scanner;

//***while loop keeping track of N-thats inputed and the
// I CAN'T FIGURE IT OUT!! =[

public class MATRIX_NxN {
public static void main(String args[]) {
  System.out.println("Enter the N value: ");
  Scanner scan = new Scanner(System.in);
  int N = scan.nextInt();
  System.out.println(" ");
  System.out.println("Enter the number you are looking for: ");
  int num = scan.nextInt();
  long startTime = System.nanoTime();
  int[][] matrix;
  matrix = new int[N][N];
  int counter = 1;
  for (int i = 0; i < matrix.length; i++) {
   for (int j = 0; j < matrix[i].length; j++) {
    matrix[i][j] = counter;//(int) (Math.random() * 100);
    counter++;
   }
  }
  System.out.println("Matrix is: ");
  for (int i = 0; i < matrix.length; i++) {
   for (int j = 0; j < matrix[i].length; j++) {
    System.out.print(matrix[i][j] + " ");
   }
   System.out.println();
  }
  
  int loc1 = 0;
  int loc2 = 0;
  for (int i = 0; i < matrix.length; i++) {
   for (int j = 0; j < matrix[i].length; j++) {
    if (matrix[i][j] == num) {
     loc1 = i;
     loc2 = j;
     long endTime = System.nanoTime();
     System.out.println("Runtime:" + String.format("%12.5f", ((endTime - startTime) / Math.pow(10, 9))));
     
    }
   }
  }
  System.out.println("Number is present at : " + loc1 + "," + loc2);
}// end main

}// end class

Explanation / Answer

import java.util.Scanner;

//***while loop keeping track of N-thats inputed and the
// I CAN'T FIGURE IT OUT!! =[

public class MATRIX_NxN {
public static void main(String args[]) {
System.out.println("Enter the N value: ");
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
System.out.println(" ");
System.out.println("Enter the number you are looking for: ");
int num = scan.nextInt();
long startTime = System.nanoTime();
int[][] matrix;
matrix = new int[N][N];
int counter = 1;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
matrix[i][j] = counter;//(int) (Math.random() * 100);
counter++;
}
}
System.out.println("Matrix is: ");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
  
int loc1 = 0;
int loc2 = matrix.length-1;
  
  
  
//as you can, the matrix would be sorted in row wise and column vise...
//so....we can search it in O(n)
int n=matrix.length;
while(loc1<n && loc2>=0)//using only one loop
{
if(matrix[loc1][loc2]==num)
{
break;//if fond breaking
}
if(matrix[loc1][loc2]>num)
loc2--;
else loc1++;
}
  
  
  
  
/*
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == num) {
loc1 = i;
loc2 = j;
long endTime = System.nanoTime();
System.out.println("Runtime:" + String.format("%12.5f", ((endTime - startTime) / Math.pow(10, 9))));




}
}
}*/
  

System.out.println("Number is present at : " + loc1 + "," + loc2);
}// end main
}// end class

output:

run:
Enter the N value:
5

Enter the number you are looking for:
5
Matrix is:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Number is present at : 0,4
BUILD SUCCESSFUL (total time: 5 seconds)

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.