Codility zadanie 2.2 -błąd systemu?

Cześć wszystkim,

mam dziwny problem z Codility z zadaniem z permutacji.
Według Codility,permutację rozumieją jako:

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

W celu spradzenia kod przechodzi test polegający na rzuceniu tylko jednej wartości.
Czy jedna wartośc to też permutacja?

Co dziwne w moim kodzie dałem warunek:

(N to liczba elementów danej nam tablicy A[k] )
if(N==1) return 1;

...i wywaliło błąd.Oczekują dla jednej wartości zwrócenia 0.
Gdy zatem zmieniłem aby przy jednej wartości zwracało 0,okazuje się ,że też źle...Jednak oczekują 1.
O co chodzi? ;0
To jakiś bład systemu?

Treść zadania:
"
A non-empty zero-indexed 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:
int solution(int A[], int N);
that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
"

Moje rozwiazanie w C:

#include <stdlib.h>

int solution(int A[], int N) {
    
    if(N<=1) return 1;
    int *tab=(int*)calloc(N,sizeof(int));
    int i;
        
    for(i=0;i<N;i++) tab[ A[i] -1 ]=1;
    for(i=0;i<N;i++) if(tab[i]==0) return 0;
    return 1;
    
} 

Dodam jeszcze ,że przy warunku " if(N==1) return 0; " twierdzą również,że tablica 100 000 wartości,każdej identycznej też powinna być permutacją,mimo ,ze w instrukcji jest napisane wyraźnie " containing each element from 1 to N once, and only once "
Bardzo prosze o pomoc.

Nic nie rozumiesz. Masz mieć w tej wejściowej tablicy jako WARTOŚCI kolejne liczby 1..N
Więc dla tablicy o 1 elemencie powinien on (element tablicy) wynosić 1. Dla tablicy o 2 elementach powinny mieć wartości 1 oraz 2 (kolejność dowolna). Więc nie każda 1-elementowa tablica jest poprawna. Tylko taka o elemencie równym 1.

edit: zresztą robisz tu panie jakieś cuda na kiju. Suma takiego ciągu arytmetycznego o n elementach i różnicy 1 to S=n*(n+1)/2. Więc jeśli zakresy danych na to pozwalają to ja bym po prostu przeiterował tablicę i odejmował elementy tablicy od S a na koniec sprawdził czy jest 0 czy też nie. (bzdury i majaki)
Jeśli zakresy są za duże to bym tą tablicę posortował i przeiterował sprawdzając czy wszystkie liczby są po kolei od 1 do N i jeśli trafi sie coś nie po kolei (albo zaczniemy od innej liczby niż 1) to zwrócił 0.

@Shalom, sprawdzenie czy suma elementów tablicy = n*(n+1)/2 nie jest wystarczające.
PoC:
A = [1,2,3,3,6];
S=15, suma elementów tablicy=15, a tablica nie jest permutacją.

Ja bym zrobił to inaczej, w jednej pętli która się wykona maksymalnie n razy:

bool b[n+1]=false; // jeżeli będzie miała długość n, nie obsłuży ostatniego elementu D;
for(i=0; i<n; i++){
  if(b[a[i]] || a[i]>n || a[i]<1) return 0;
  b[a[i]]=true;
} // nie musisz nic więcej robic
return 1;

tak chyba będzie bardziej najbardziej optymalne, bez liczenia jakichkolwiek sum :)

No tak, oczywiście zapomniałem o tym że mogą tam być błędne liczy a dobra suma :P @_naf ale nadal masz O(n) dodatkowej pamięci :P
Da sie to zrobić bez pamięci, korzystając tylko z wejściowej tablicy, bo ona przecież ma dokładnie tyle pamieci ile nam trzeba.
Bierzemy A[0] a następnie skaczemy sobie do elementu tablicy A[A[0]], zapamiętujemy sobie tą wartość tabllicy, zerujemy ten element i skaczemy znów do A[zapamietana_wartosc-1] i powtarzamy sobie te czynności. Jeśli skoczymy na wyzerowany element to znaczy że tablica jest niepoprawna bo dwa elementy są identyczne. Jeśli chcemy skoczyc poza tablicę to wejście nie jest poprawne bo jest tam za duża wartość gdzieś.
Niestety jest tu głupi przypadek szczególny - pozycja startowa. W tablicy są cykle więc może tak być że skoczymy na element z którego startowaliśmy (np. na 0) i wtedy musimy sobie wybrać nowy element startowy z tablicy (jakiś jeszcze nie wyzerowany).

Niestety to sprawia że pesymistycznie algorytm robi sie O(n²) przez samo to głupie szukanie nowej pozycji startowej (pesymistycznie mamy cały czas cykle po 2 kolejne elementy ;]).

Podsumowując: albo bierzemy O(n) + O(n) pamięci albo bierzemy O(nlogn) w pamięci stałej.

bool solution (int *Array, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        if (Array[i] < 1 || Array[i] > n)
            return false;
    }

    for (size_t i = 0; i < n; ++i) {
        if (Array[abs(Array[i]) - 1] < 0)
            return false;
        
        Array[abs(Array[i]) - 1] *= (-1);
    }
    
    for (size_t i = 0; i < n; ++i) {
        if (Array[i] > 0)
            return false;
    }
    return true;
}

@Shalom: Jestem przekonany, że to działa. W skrócie:
pętla pierwsza sprawdza, czy wszystkie liczby są z odpowiedniego zakresu.
w pętli drugiej bierzemy każdy element Array[i] i w miejscu przez niego wskazywanym - 1 zmieniamy znak liczby. To informuje nas o tym, ze liczba Array[i] wystąpiła w tablicy. Jeśli wystąpi drugi raz - pierwszy if w tej pętli to wyłapie.
w trzeciej pętli sprawdzamy, czy wszystkie liczby zostały oznaczone jako takie, które wystąpiły w tablicy. Wiemy, że jeśli coś wystąpi więcej niż raz, to zwrócimy false (pętla druga). Jeśli natomiast któraś z liczb nie wystąpi w ogóle - odpowiednie miejsce w tablicy nie będzie ujemne.

Czyli podsumowując: każda liczba Array[i] jest z odpowiedniego zakresu + każda wystąpiła dokładnie jeden raz. No i jest ich odpowiednia ilość, to oczywiste.

bool is_permutation(int Arr[], int size)
{
	std::sort(Arr, Arr + size);
        if (Arr[0] != 1)
        {
              return false;
        }
	for (int i = 0; i < size; ++i)
	{
		if (i + 1 <= size)
		{//check that we will not access index out of bounds

			if (Arr[i + 1] - Arr[i] != 1)
			{//1 - 0 == 1, 2 - 1 == 1, etc
				return false;
			}
		}
	}
	return true;
}

Modern C++ version (dzieki dla @fasadin, tylko szczera krytyka pozwala nam na poprawe i udoskonalenie, thanks bro! ;) ):

bool is_permutation_MC(int Arr[], int size)
{
	std::set<int> aSet{ Arr, Arr + size };
	if (*aSet.cbegin() != 1)
	{
		return false;
	}
	for (auto beg = aSet.cbegin(), end = aSet.cend(); beg != std::prev(end); ++beg)
	{
		if ((*std::next(beg) - *beg != 1))
		{//1 - 0 == 1, 2 - 1 == 1, etc
			return false;
		}
	}
	return true;
}