Advertisement
Kali_prasad

find unflipped cells in binary matrix

Dec 31st, 2024 (edited)
234
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.19 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. /*
  4.  
  5. given an N x M binary matrix , there are Q queries in each query which is i,j a position in the matrix
  6. you need to select the row i and column j and flip the values ,
  7. v1 - thing is the i,j position changes only one time
  8. v2 - thing is the i,j position changes twice
  9. find the unchanged cells after all the q queries
  10.  
  11.  
  12.  
  13. note - here the q queries use 0 based indexing
  14.  
  15.  */
  16.  
  17.  /*
  18.  
  19. //inputs for array , given you the N x M and then the binary matrix and then q queries
  20. 3 3
  21. 0 0 1
  22. 0 1 0
  23. 1 0 0
  24. 2
  25. 2 0
  26. 1 1
  27.  
  28. expected output -
  29. The result is 5
  30.  
  31.  
  32.  */
  33.  
  34.  
  35. @SuppressWarnings("unused")
  36. public class A20243012_googleOA {
  37.  
  38.     static Scanner sc = new Scanner(System.in);
  39.  
  40.     private static int[] getArray() {
  41.         String[] sArr = sc.nextLine().split(" ");
  42.         int[] arr = Arrays.stream(sArr).mapToInt(Integer::parseInt).toArray();
  43.         return arr;
  44.     }
  45.  
  46.     private static char[] getCharArray() {
  47.         String[] sArr = sc.nextLine().split(" ");
  48.         char[] cArr = new char[sArr.length];
  49.         for (int i = 0; i < sArr.length; i++) {
  50.             cArr[i] = sArr[i].charAt(0); // Take the first character of each string
  51.         }
  52.         return cArr;
  53.     }
  54.  
  55.     private static int getMax(int[] arr) {
  56.         int currMax = Integer.MIN_VALUE;
  57.         for (int curr : arr) {
  58.             currMax = Math.max(currMax, curr);
  59.         }
  60.         return currMax;
  61.     }
  62.  
  63.     public static void main(String args[]) {
  64.         // prepare the inputs
  65.  
  66.         int[] arr = getArray();
  67.         int N = arr[0];
  68.         int M = arr[1];
  69.         int[][] binMat = new int[N][M];
  70.         for(int i = 0;i<N;i++){
  71.             binMat[i] = getArray();
  72.         }
  73.         int q = getArray()[0];
  74.         // System.out.println("q is"+q);
  75.         HashMap<Integer,Integer> rowMap = new HashMap<>();
  76.         HashMap<Integer,Integer> colMap = new HashMap<>();
  77.         HashMap<Pair,Integer> pairMap = new HashMap<>();
  78.         for(int i=0;i<q;i++){
  79.             int[] query = getArray();
  80.             Pair pair = new Pair(query[0],query[1]);
  81.             rowMap.put(pair.row,rowMap.getOrDefault(pair.row,0)+1);
  82.             colMap.put(pair.col,colMap.getOrDefault(pair.col,0)+1);
  83.             pairMap.put(pair,pairMap.getOrDefault(pair,0)+1);
  84.         }
  85.         // System.out.println("hii");
  86.  
  87.         int changedCount=0;
  88.         for(int i=0;i<N;i++){
  89.             for(int j=0;j<M;j++){
  90.                 Pair pair = new Pair(i,j);
  91.                 int rowFreq = rowMap.getOrDefault(pair.row,0);
  92.                 int colFreq = colMap.getOrDefault(pair.col,0);
  93.                 int pairFreq = pairMap.getOrDefault(pair,0);
  94.  
  95.                 int currFlipped =(rowFreq)+(colFreq)-pairFreq;//for v2 just remove the pairFreq
  96.                 if(currFlipped%2!=0){
  97.                     // System.out.println(" pair.row "+pair.row+" pair.col "+pair.col+" is changed ");
  98.                     changedCount+=1;
  99.                 }
  100.             }
  101.         }
  102.         int res = N*M-changedCount;
  103.        
  104.         System.out.println("The result is " + res);
  105.  
  106.     }
  107. }
  108.  
  109. class Pair{
  110.     int row;
  111.     int col;
  112.     public Pair(int i,int j){
  113.         this.row = i;
  114.         this.col = j;
  115.        
  116.     }
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement