'PermCheck codility. O(N) time complexity

Hi i have this solution for PermCheck codility. Here is the link which includes the question: https://codility.com/demo/results/demo73YNCU-8FK/

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)? Thankyou.

Code here for shortcut:

    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;
c++sharpperformancealgorithmtime-complexity


Solution 1:[1]

Here is my 100/100 answer:

same Idea as @fejesjoco

https://codility.com/demo/results/demoNR485D-33P/

You can change int to long to get performance.

    public int solution(int[] A)
    {
        // idea: add to set,dictionary. Count the size and compare to N.
        // dedupe data when needed. 
        var set = new HashSet<int>();
        var max = int.MinValue;

        foreach (var item in A)
        {
            if (set.Contains(item)) return 0;

            set.Add(item);
            if (item > max) max = item;
        }
        return set.Count == max ? 1 : 0;
    }

Solution 2:[2]

This is my solution that scored 100% in correctness and performance.

def solution(A): arraylength = len(A)

if (arraylength > 100000):
    raise ValueError("Out of bound range")    

arr = sorted(A)

for i in range(arraylength):

    if (arr[i] != i+1):
        return 0

return 1

Solution 3:[3]

I know that this questions is asked long time ago but it is still active in codility.

Possible solution:

public int solution(int[] A)
{
    return (Enumerable.Range(1, A.Length).Except(A).Count() == 0) ? 1 : 0;
}

Solution 4:[4]

Following the suggestion by fejesjoco,

Boolean[] bln = new Boolean[A.Length];       

for (int i = 0; i < A.Length; i++)
{
    if (A[i] > A.Length) // more than array length
        return 0;
    if (bln[A[i]-1]) // same value twice
        return 0;
    bln[A[i]-1] = true;
}
return 1;

Solution 5:[5]

This was my solution, it scored 100%. Do not forget to add "using System.Linq".

int distinctLength = A.Distinct().ToArray().Length;
// The array length should equal to the distinct array length which is also the maximum value in array A.
if (A.Length == distinctLength && distinctLength == A.Max()) { return 1; }
return 0;

Solution 6:[6]

Swift Solution 100% 

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)

    let sorted = A.sorted()

    for (index, value) in sorted.enumerated() {

        if index+1 != value {

            return 0
        }
    }

    return 1
}

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 CodeFarmer
Solution 2 Rehan Ahmad
Solution 3 ASisic
Solution 4 siddharth
Solution 5 Mohamed Ali Eldin
Solution 6 Pushpendra Singh

Related Questions