CODEWITHSUNDEEP
cmultidimensional-array
Munchdong
Munchdong

Reputation: 153

How to check that an array contains 1 to n^2 integers?

Let's say I want to check an 3x3 array and I want it to contain all the numbers from 1 to 9. I cant think of any efficient way other than the one I've written it down below. Is there a better way to solve this question?

int i, size, row, col, num = 1, valid = 0;

for(i=0; i<size*size; i++)
    for(row=0; row<size; row++)
        for(col=0; col<size; col++)
            if(num == arr[row][col]) {
                num++;
                valid++;
            }

Upvotes: 2

Views: 556

Answers (4)

nhouser9
nhouser9

Reputation: 6780

Yes. There is a better way.

It would be more optimal to use a boolean array instead of a third loop. Keep an array of booleans, initially all set to false. For each number found, mark the corresponding index in the array to true. At the end of your row and column loops, if all entries in the array are set to true, you found all the numbers.

To optimize even further, you could declare a counter variable. Each time you find a number, use your boolean array to check if that number was already found. If not, increment the counter. At the end of the loop, if the counter is 9, you have found 9 unique numbers.

You can even terminate early if you find a duplicate. This will increase performance further but only works if the number of unique numbers to find and the number of spaces for them to inhabit is the same. I.e. if you have 18 spaces and want to check for all numbers 1-9 this does not work.

Upvotes: 3

blazs
blazs

Reputation: 4845

Another idea would be to loop through the k-times-k array and sum all the elements. Ensure that the resulting sum equals 1+2+...+n = n*(n+1) / 2, where n = k*k. This coupled with the condition that all elements be unique (and positive) ensures that the array contains all and only the elements in {1,2,...,n}.

For n=9 you'd check that the sum equals 45. For small n you can use bit masks to check whether a number has been seen already: if (n & (1 << current_number)) { seen; } else {not yet seen; mark as seen via n |= (1 << current_number); }

Upvotes: 1

Lundin
Lundin

Reputation: 213678

The outer loop isn't needed and you can stop searching when you find the first non-matching item. Unless you for some reason need a list of all the non-matching items, which doesn't seem to be the case(?).

Further micro-optimizations can be done if you know that the dimensions are always small. In this example they are assumed to be <256:

#include <stdint.h>
#include <stdbool.h>

bool is_arr_ok8 (uint_fast8_t row, uint_fast8_t col, int arr[row][col])
{
  uint_fast8_t count=1;

  for (uint_fast8_t r=0; r<row; r++)
  {
    for(uint_fast8_t c=0; c<col; c++)
    {
      if(arr[r][c] != count)
      {
        return false;
      }
      count++;
    }
  }

  return true;
}

The most important here is that the inner-most loop corresponds to the inner-most dimension. You could as well do it the other way around, and it wouldn't affect the algorithm, but it would give much worse data cache performance.

Upvotes: 0

Ed Heal
Ed Heal

Reputation: 59997

How about:

bool nums[9] = {false, false, false, false, false, false, false, false, false};

for (int row = 0; row < 3; ++row) {
   for (int col =0; col < 3; ++col) {
      if (arr[row][col] < 1 || arr[row][col]> 9 || nums[arr[row][col] -1]) {
        // Number is out of range or previous it)
        break;
      }
      nums[arr[row][col] -1] = true;
   }
}

Where nums store true if the corresponding value has been found.

Upvotes: 1

Related Questions