5
\$\begingroup\$

I have this solution for Codility's PermCheck problem. In summary, the task is to check whether array A contains each number in \$1 \ldots N\$ exactly once.

I got 100% for it but I got a time complexity of \$O(N * log(N))\$ or \$O(N)\$. How could I make this code \$O(N)\$? Could you also give a brief description of what makes code \$O(N)\$?

Array.Sort(A);
if(A[0] == 1 && A.Length == 1) return 1;
if(A[0] != 1) return 0;

int n = 0;
for(int i = 0; i < A.Length; i++)
{    
    if(i < A.Length - 1)
    {
        if(A[i+1] == A[i] + 1)
        {
            n += 1;
        }
        else 
        {
            return 0;   
        }
    }
}
return 1;
\$\endgroup\$
  • \$\begingroup\$ Taken from the site you linked: "Copyright 2009–2014 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited." I am not sure whether you are even allowed to ask this question... \$\endgroup\$ – Vogel612 Nov 9 '14 at 17:51
  • 6
    \$\begingroup\$ Well i'm just asking to review my code from a question which they have public. Besides i'm not exactly the first person in the queue to ask for a review of their code from this site. So if you could help and just let me know at the very least how this code doesn't truly represent an O(N) time complexity :) Cheers \$\endgroup\$ – HusCode Nov 9 '14 at 17:56
10
\$\begingroup\$

This code involves sorting an array of \$N\$ elements, so it has \$O(N * log N)\$ time complexity. To achieve \$O(N)\$ time complexity, you need to avoid sorting input data. Instead, you can create an array of \$N\$ bools to check that each number from \$1\$ to \$N\$ is present in the input array.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thankyou. I managed to solve it using a boolean array that you suggested and you gave a clear answer. Cool! \$\endgroup\$ – HusCode Nov 9 '14 at 18:04
4
\$\begingroup\$

Although I don't know C#, I can make some observations based on other C-family languages.

Firstly, the code appears incomplete. I'll have to assume that this is the body of a function declared to accept an array A and return a boolean.


Array.Sort(A);

Obviously, sorting is O(n log n) in the general case, so the method can't scale better than that.


if(A[0] == 1 && A.Length == 1) return 1;
if(A[0] != 1) return 0;

There's no need to test A[0] twice, if we swap the order of these tests. But we do need to check that A is not empty before accessing A[0].


int n = 0;

What's n for? It's assigned but never used.


for(int i = 0; i < A.Length; i++)
{    
    if(i < A.Length - 1)
    {
         /// code
    }
}

That simplifies to

for(int i = 0;  i < A.Length - 1;  i++)
{
     /// code
}

The whole loop and the prior tests (for the A.Length <= 1 cases) simplifies to just

for (int i = 0;  i < A.Length;  i++)
    if (A[i] != i+1)
        return 0;
return 1;

No need for those A[0] checks at all.


My version:

Array.Sort(A);
for (int i = 0;  i < A.Length;  ++i)
    if (A[i] != i+1)
        return 0;
return 1;

Algorithm improvements

As other answers hint, to get O(n) speed (at a cost of O(n) memory use), we'll want to allocate a bitmap of size A.Length, and populate the entries as we go. We can exit early whenever we see an out-of-range value or a repeated value (i.e. an already set bit). If no value causes early exit, then we must have seen every integer in the range exactly once.

That would look something like:

// UNTESTED!
int N = A.Length;
bool[] b = new bool[N];
for (int i = 0;  i < N;  ++i) {
     int x = A[i] - 1;
     if (x < 0 || x >= N || b[x])
         return 0;
     b[x] = true;
}
return 1;
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [1..1,000,000,000].

So, who said that you will have a disordered sequence of 1, 2, 3, 4... You might get N = 6, and array A[1, 4, 5, 7, 1000, 6].

So, your solutions are wrong. I suggest you to use HashTable to store a value and check if it has one or not.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

1 + 2 + ... + n = n * (n + 1) / 2, for example, 1 + 2 + 3 = 3 * (3 + 1)/2 = 6, so the \$O(N)\$ is that:

  1. sum the array, O(n) (no sorting)
  2. check sum == n * (n + 1) / 2
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Interesting suggestion, but there are many arrays that could sum to the same value (e.g. {0, 0, 6}). \$\endgroup\$ – Toby Speight Jan 8 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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