6
\$\begingroup\$

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;
}
\$\endgroup\$
8
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I asked a general question about this kind of reviews where you challenge the challenge itself :) -> codereview.meta.stackexchange.com/questions/9345/… \$\endgroup\$ – dfhwze Sep 23 at 19:50
  • 1
    \$\begingroup\$ Good idea. My thinking was to bridge the gap between a good solution to the challenge, and good "real life" code. I'm interested in how valuable the community finds that type of feedback. \$\endgroup\$ – benj2240 Sep 23 at 19:53
  • \$\begingroup\$ So am I. I've also commented on challenge requirements in some of my reviews, but never to this extend. I find it an interesting way of reviewing :) \$\endgroup\$ – dfhwze Sep 23 at 19:56
  • 5
    \$\begingroup\$ Single-letter variable names are almost never a good idea. Just to extend, they are a good idea when dealing with maths. E.g. Multiply(int a, int b) is perfectly acceptable because "number1" etc isn't better. But the answer is correct that for dore general data purposes, single letter variables are usually bad. \$\endgroup\$ – Flater Sep 24 at 9:11
  • 2
    \$\begingroup\$ The Meta question brought me here. The only change I would suggest is to put the Silly Requirement points into a single section Silly Requirements after the observations about the OP's code, not before. Perhaps make the silly requirements a list of bullet points. I don't see a problem with challenging the challenge. \$\endgroup\$ – pacmaninbw Sep 27 at 13:17
2
\$\begingroup\$

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;
    }
}
\$\endgroup\$

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.