0

I have a question here and I am trying to find a solution of it. But I want to see some other opinions as well.

The problem is the following:

There is a matrix NxN which holds integer numbers. You should count all the different numbers in the matrix with the following conditions:

  • If two-or-more same numbers are adjacent (left, right, above, below) each of other it counts as one.

Example of the matrix:

1 2 3 4

1 1 2 4

5 6 2 2

So for the above example there are: 7 different numbers because at the position of matrix : [1,1][2,1][2,2] there are 1s which has the condition of the problem true therefore these 3 numbers counts as one, at position [1,4][2,4] there are 4s so counts as one as well, and finally at positions [2,3],[3,3] and [3,4] there are 3s so count as one number.

My thought is to set the duplicate numbers to negative and then count only the positives, but I am not sure if that will work for all cases including and the corner cases.

My Code:

public class matrix
{
   public static void main(String[] args)
   {
      int[][] arr = 
      { 
          {1, 2, 3, 4}, 
          {1, 1, 2, 4},
          {5, 6, 2, 2},
      };

      for(int row = 0; row < arr.length; ++row)
      {
         for(int col = 0; col < arr[row].length; ++col)
         {
            //top
            if(row!=0)
            {
               if((arr[row][col] == arr[row-1][col]) || (Math.abs(arr[row][col]) == arr[row-1][col]) || (arr[row][col] == Math.abs(arr[row-1][col])))
               {
                  arr[row-1][col] = -arr[row-1][col];
               }
            }

            //botom
            if(row!=arr.length-1)
            {
               if(arr[row][col] == arr[row+1][col] || Math.abs(arr[row][col]) == arr[row+1][col] || arr[row][col] == Math.abs(arr[row+1][col]))
               {
                  arr[row+1][col] = -arr[row+1][col];
               }
            }

            //left
            if(col!=0)
            {
               if(arr[row][col] == arr[row][col-1] || Math.abs(arr[row][col]) == arr[row][col-1] || arr[row][col] == Math.abs(arr[row][col-1]))
               {
                  arr[row][col-1] = -arr[row][col-1];
               }
            }

            //right
            if(col!=arr[0].length-1)
            {
               if(arr[row][col] == arr[row][col+1] || Math.abs(arr[row][col]) == arr[row][col+1] || arr[row][col] == Math.abs(arr[row][col+1]))
               {
                  arr[row][col+1] = -arr[row][col+1];
               }
            }
         }
      }


      for(int row = 0; row < arr.length; ++row)
      {
         for(int col = 0; col < arr[row].length; ++col)
         {
            System.out.print(arr[row][col] + " ");
         }

         System.out.println();
      }
   }
}

Expected Outcome:

 1  2  3  4

-1 -1  2 -4

 5  6 -2 -2

Code Outcome:

 1  2  3 -4

 1 -1 -2 -4

 5  6  2 -2
8
  • If your solution works, whats the problem?
    – user40980
    Commented Dec 3, 2014 at 22:58
  • Its look like my though is poor programming, or something. I want to see some more advanced approach to improve my logical thinking. Commented Dec 3, 2014 at 22:59
  • Write the code that you write. If I came up with a beautiful advanced solution and you handed this homework in (I assume its homework) or tried to find a bug in it, you wouldn't be able to. You need to write code that you are able to maintain. So write it. See if it works. If it doesn't work, then you have a problem to ask about. Just asking us to come up with ideas for how to solve it isn't a good approach because we may come up with things that are completely foreign to you or not idiomatic for the language you are working in.
    – user40980
    Commented Dec 3, 2014 at 23:00
  • Okay, is not homework. I am solving some programming problems to prepare for competitions where such questions exist. Commented Dec 3, 2014 at 23:02
  • 1
    Sit down, design it, write some code. Have it work. Then submit the code to codereview.SE to have them critique and analyze the code. Getting algorithms and approaches that you don't understand or can modify to suit the design issues that you encounter will make it harder for you in the long run to solve these competitions.
    – user40980
    Commented Dec 3, 2014 at 23:04

1 Answer 1

1

My thought is to set the duplicate numbers to negative and then count only the positives

It sounds like you're using negatives as an "isDuplicate" flag. This is a great example of the difference between competitive programming and professional programming.

In a competitive environment, you're trying to optimize the time it takes to write the program. Declaring more variables (e.g. declaring an explicit "isDuplicate" data-structure) would require t.y.p.in.g. m.o.r.e. c.o.d.e. w.h.i.c.h. t.a.k.e.s. m.o.r.e. t.i.m.e. You don't have to declare anything new to use negatives, so you don't have to type as much, so it feels like that might be a productive approach.

In a professional environment, I would never consider using negatives this way. Use negatives if you actually want to perform arithmetic on negatives. There are several reasons:

  • Negatives have peculiar properties -- e.g. "1 + -1 == 0" and "-1 * -1 == +1"; these properties are nonsensical for the isDuplicate flag.
  • Most other developers (who review/update your code) wouldn't readily intuit the idea that "negative" means "isDuplicate" (unless, by some miracle, they were also competitive coders working from the same narrow problem-definition in the same narrow time-frame).
  • Requirements change. Today, "isDuplicate" is important information. Tomorrow, "isPrime" might be important information. Next week, we might decide to drop the "isDuplicate" information. The only way to keep these things straight is to give them very clear names.

As it happens, your bug does in fact relate to one of those peculiar properties of negative numbers. (I'll bite my tongue on the specific problems because, as the commenters noted, it's good for you to work through it.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.