Codility's Permutation Check in C#

Question

I've made a few things in Java, and now I'm learning C#.
The code passes the tests with 100% final score.
I want to know what things can be improved in my code.

Task description

---

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2 is a permutation, but array A such that:

A[0] = 4
A[1] = 1
A[2] = 3 is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2 the function should return 1.

Given array A such that:

A[0] = 4
A[1] = 1
A[2] = 3 the function should return 0.

Write an efficient algorithm for the following assumptions:

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].

public static int solution(int[] A)
{
    int[] orderedPermut = new int[A.Length];
    int[] unrepeated = new int[A.Length];
    int orderedPermutSum = 0, unrepeatedSum = 0;
    for ( int i = 0; i < A.Length; i++ )
    {
        orderedPermutSum += i + 1;
        orderedPermut[i] = i + 1;
        if ( A[i] >= A.Length + 1 || unrepeated[ A[i] - 1 ] != 0 )
            /*number is greater than A's length, or it's repeated,
            /*therefore,A's not a permutation.*/
            return 0;
        else
        {
            unrepeated[A[i] - 1] = A[i];
            unrepeatedSum += A[i];
        }
    }
    if ( orderedPermutSum == unrepeatedSum )
    {
        return 1;
    }
    return 0;
}

Answer 1

One of the unfortunate things you'll notice about coding challenges is that the requirements often force you to write code that isn't ideal. I'm going to call these out, even though in this case they're outside of your control.

Silly requirement: The method is named solution. This name tells us nothing about the behavior of the function. Also (although less importantly), it goes against the C# method naming convention of PascalCase. A much better name would be something like IsPermutation.

Silly requirement: The parameter is named A. Single-letter variable names are almost never a good idea. Also (although less importantly), it goes against the C# parameter naming convention of camelCase. It's hard to be descriptive about the context here (since it's just a coding challenge and not a "real life" business problem), but even something like values would be better.

Silly requirement: The return type of the function is int. The given array is either a permutation of 1..N or it isn't. We don't have a range of possible return values; we have a true/false condition. A better return type would be bool.

Algorithm inefficiency: There's no need to initialize two new int[]. As you discovered, one new array is sufficient to track unique values.

Algorithm inefficiency: Again, you've already discovered this. If an array has the correct elements in some order, its sum will necessarily match that of the unordered array. Meanwhile the converse is not true; there are many arrays with the same sum which are not permutations. So you needn't bother tracking the sum at all.

Syntax: If you take only one piece of my advice, let it be this one: for loops are not the answer. If you are iterating over the indexes of an array, and the only thing you use the index for is to grab the ith element, use a foreach. The situation where you actually need to know the index, and therefore need a for loop, is very rare.

Semantics: Does an array of int take less space in memory than an array of bool? I don't know, and I don't care. If all I'm tracking is true/false values, I'm going to choose a bool[]. Because that choice tells the person reading the code why I created the variable.

Formatting: Another major difference between formatting conventions in C# and Java (besides the PascalCase/camelCase conventions I already mentioned) is C#'s convention of putting opening curly braces on the next line (known as K&R style).

---

With all of that advice applied, and some XML documentation comments (which enable Intellisense information when hovering or typing in Visual Studio), we'll end up with something like this:

/// <summary>
/// Check whether the given array contains each integer 1..N exactly once.
/// </summary>
/// <returns>
/// True if <paramref name="values" /> is a permutation of 1..N,
/// False otherwise.
/// </returns>
public static bool IsPermutation(int[] values)
{
    var seen = new bool[values.length];

    foreach (var value in values)
    {
        if (value < 1 || value > values.length)
        {
            // Out of range: not a permutation
            return false;
        }
        else if (seen[value - 1])
        {
            // Duplicated value: not a permutation
            return false;
        }
        else
        {
            // Value is OK. Mark as seen.
            seen[value - 1] = true;
        }
    }

    // All values in range, no duplicates: a valid permutation
    return true;
}

Answer 2

I checked the solution to this problem in codesays (answered by Sheng).
One thing I can improve from his better solution is that he followed the same approach, but didn't check if the sum of a proper and ordered permutation was correct, so he didn't use an ordered array.
I used two counters, one that I knew was correct, and another one that could go wrong, but if I think about it, if no elements were repeated, nor out of range, then checking for the sum to be right wasn't necessary, because it must be a permutation if that was the case. Checking for negative numbers was something I could also do, and then decide it was not a permutation, no tests tried arrays with negative numbers, though

class Solution {
    public static int solution(int[] A) {
        int[] counter = new int [A.length];
        for(int i= 0; i< A.length; i++){
            if (A[i] < 1 || A[i] > A.length) {
                // Out of range
                return 0;
            }
            else if(counter[A[i]-1] == 1) {
                // met before
                return 0;
            }
            else {
                // first time meet
                counter[A[i]-1] = 1;
            }
        }
        return 1;
    }
}