проверка наличия в массиве чисел от 0 до длины -1 в C

Question

У меня есть задание, и я буду рад, если вы сможете помочь мне с одним вопросом в этом задании, у меня есть вопрос, который звучит так:

напишите функцию, которая получаетмассив и его длина.Цель функции - проверить, есть ли в массиве все числа от 0 до длины -1, в противном случае функция вернет 1 или 0 в противном случае. Функция может пройти через массив только один.Вы не можете отсортировать массив или использовать счетный массив в функции

Я написал функцию, которая вычисляет сумму и произведение значений и индексов массива

int All_Num_Check(int *arr, int n)
{
 int i, index_sum = 0, arr_sum = 0, index_multi = 1, arr_multi = 1;

 for (i = 0; i < n; i++)
  {
    if (i != 0)
       index_multi *= i;
    if (arr[i] != 0)
       arr_multi *= arr[i];

    index_sum += i;
    arr_sum += arr[i];
  }

 if ((index_sum == arr_sum) && (index_multi == arr_multi))
    return 1;

 return 0;
}

, то есть:length = 5, arr = {0,3,4,2,1} - это правильный массив длины = 5, arr = {0,3,3,4,2} - это неправильный массив

к сожалению, эта функция не работает должным образом во всех различных случаях изменения числа.то есть: длина = 5, {1,2,2,2,3}

спасибо за вашу помощь.

Answer 1

Я немного подумал, а потом понял, что это очень противоречивая проблема.Недопустимые вещи:

1. Использование массива подсчета.
2. Использование сортировки.
3. Использование более одного прохода к исходному массиву.

Следовательно, я придумал этот подход использования операции XOR для определения результатов.

1. a ^ a = 0
2. a ^ b ^ c = a ^ c ^ b.

Попробуйте это:

int main(int argc, char const *argv[])
{
    int arr[5], i, n , temp = 0;
    for(i=0;i<n; i++){
        if( i == 0){
            temp = arr[i]^i;
        }
        else{
            temp = temp^(i^arr[i]);
        }
    }
    if(temp == 0){
        return 1;
    }
    else{
        return 0;
    }
}

Чтобы выполнить условие, упомянутое в задаче, каждое число должно появляться один раз.
Теперь, когда число лежит в диапазоне [0,.. n-1], переменная цикла также будет иметь такой же возможный диапазон.
Переменная temp изначально установлена ​​на 0.
Теперь, если все числа появляются таким образом, то каждое число будет появляться дважды дважды.
И если XOR при одинаковом числе дважды, то получится 0.
Итак, если в конце, когда весь массив пройден и получен ноль, это означает, что массив содержит все числа сразу по одному.
В противном случае, существует несколько копий числа, следовательно, это не будет оцениватьсядо 0.

Answer 2

Проверка суммы и продукта недостаточна, как показывает ваш контрпример.

Простым решением было бы просто отсортировать массив и затем проверить, что в каждой позиции i, a[i] == i.

Редактировать: исходный вопрос был отредактирован так, что сортировка также запрещена,Предполагая, что все числа положительны, следующее решение «помечает» числа в требуемом диапазоне путем отрицания соответствующего индекса.Если какая-либо ячейка массива уже содержит помеченный номер, это означает, что у нас есть дубликат.

int All_Num_Check(int *arr, int n) {
  int i, j;

  for (i = 0; i < n; i++) {
      j = abs(arr[i]);
      if ((j >= n) || (arr[j] < 0)) return 0;  
      arr[j] = -arr[j];
  }

  return 1;
}