Как насчет того, чтобы использовать XOR с четными и нечетными числами отдельно. Думайте о разрядном уровне не само целочисленное значение.

bool is_same(const int* a, const int* b, int len)
{
    int even_xor = 0; 
    int odd_xor = 0;

    for(int i=0;i<len;++i)
    {
        if(a[i] & 0x01) odd_xor ^= a[i];
        else even_xor ^= a[i];

        if(b[i] & 0x01) odd_xor ^= b[i];
        else even_xor ^= b[i];
    }

    return (even_xor == 0) && (odd_xor == 0);
}

я не думаю, что объяснился в своем исходном сообщении хорошо (ниже сплошной линии). Для входа [1 2 3 4 5], например, алгоритм вычисляет сумму:

-1 + 2 - 3 + 4 - 5 

, который должен быть равен

-1^5 * ceil(5/2)

псевдокод ниже шоу, как проверяются векторы, которые не начинаются в 1. алгоритм обрабатывает случаи, где входной вектор не отсортирован, и/или это содержит дубликаты.

следующий алгоритм решает проблему путем вычисления переменных сумм векторных элементов:

-1 + 2 - 3 + 4 - 5 + .... + m = (-1)^m * ceil(m/2)

то, где перекрывают , окружает к самому близкому целому числу. Другими словами, нечетные числа вычтены из рабочих общих количеств, и четные числа добавляются к нему.

function test(data, m)
    altSum = 0
    n = Inf
    mCheck = -Inf
    for ii = 1:m
    {
        if data(ii) < n
            n = data(ii)
        if data(ii) > mCheck
            mCheck = data(ii)
        altSum = altSum + (-1)^data(ii) * data(ii)
    }
    if ((mCheck-n+1!=m) || (-1)^(n+m-1) * ceil((n+m-1)/2) - ((-1)^(n-1) * ceil((n-1)/2)) != altSum
        return false
    else
        return true

Линейный вовремя, постоянный в решении для пространства для int m

пространство Constant достигается путем использования знакового бита. Это может быть сделано для любого изменяемого int диапазон, если m [меньше чем 114] т.е. когда входной диапазон [n, n+m) может быть смещен к [1, m+1) диапазон, если n не положительно. На практике предварительное условие почти всегда верно, если введенный изменяемо.

/** gcc -std=c99 ... */
#include <assert.h>
#include <iso646.h>  // and, or
#include <limits.h>  // INT_MIN
#include <stdbool.h> // bool
#include <stdlib.h>  // abs()

bool inrange(int m; int a[m], int m, int n)
{
  /** Whether min(a[]) == n and max(a[]) == n+(m-1)
  */
  if (m == 0) return true; // empty range is a valid range

  // check out-of-range values
  int max = INT_MIN, min = INT_MAX;
  for (int i = 0; i < m; ++i) {
    if (min > a[i]) min = a[i];
    if (max < a[i]) max = a[i];
  }
  return (min == n and max == n+(m-1));
}

bool isperm_minus2(int m; int a[m], int m, int n)
{
  /** O(m) in time, O(1) in space (for 'typeof(m) == typeof(*a) == int')

      Whether a[] is a permutation of the range [n, n+m).

      feature: It marks visited items using a sign bit.
  */
  if (not inrange(a, m, n))
    return false; // out of range

  assert((INT_MIN - (INT_MIN - 1)) == 1); // check n == INT_MIN
  for (int *p = a; p != &a[m]; ++p) {
    *p -= (n - 1); // [n, n+m) -> [1, m+1)
    assert(*p > 0);
  }

  // determine: are there duplicates
  bool has_duplicates = false;
  for (int i = 0; i < m; ++i) {
    const int j = abs(a[i]) - 1;
    assert(j >= 0);
    assert(j < m);
    if (a[j] > 0)
      a[j] *= -1; // mark
    else { // already seen
      has_duplicates = true;
      break;
    }
  }

  // restore the array
  for (int *p = a; p != &a[m]; ++p) {
    if (*p < 0) 
      *p *= -1; // unmark
    // [1, m+1) -> [n, n+m)
    *p += (n - 1);        
  }

  return not has_duplicates; // no duplicates? (+ inrange)
}

Я не думаю, что необходимо использовать суммы вообще. Просто проверьте минимум и максимум и проверку на простофиль. Проверка простофиль является более твердой частью, так как Вы не знаете n заранее, таким образом, Вы не можете отсортировать в одной передаче. Для работы вокруг этого ослабьте условие на (edit:destination) массив. Вместо того, чтобы требовать, чтобы он был отсортирован, пойдите для циклического сдвига отсортированной последовательности, так, чтобы массив пошел [k, k+1..., n+m-2, n+m-1, n, n+1..., k-2, k-1] для некоторого k.

С условием выше, можно предположить, что [0] уже находится в правильном положении, тогда правильное положение для элемента d (d-a[0]) mod m, принимая основанную на нуле индексацию массива. Например, с [4???] можно ожидать [4,5,6,7] или [4,1,2,3] или [4,5,6,3] или [4,5,2,3].

Тогда просто сканируют массив однажды, помещая каждый элемент в его расчетное положение, обновляя минуту и макс. и проверяя на столкновения. Если нет никаких столкновений и max-min=m, то условие соблюдают, иначе это - ложь.

Если это было опечаткой, и вопрос обо всех числах, находящихся в диапазоне 1... n вместо этого, то:

def try_arr(arr):
    n = len(arr)
    return (not any(x<1 or x>n for x in arr)) and sum(arr)==n*(n+1)/2

$ print try_arr([1,2,3])
True

$ print try_arr([1,3,1])
False

$ print try_arr([1,2,4])
False

Примечания:

• я использую определение от исходной версии, которую числа запускают от 1. Верный код может быть изменен для составления запуска с другого числа.

• , Если размер массива (n) был известен, Вы могли бы изменить это к потоковым данным из, например, ввести файл и не использовать почти память (1 временная переменная в сумме () и 1 переменная для текущего объекта, взятого от потока)

• , любой () является новым в python 2.5 (но у Вас есть альтернативные способы выразить то же самое в более ранних версиях Python)

• , это использует O (n) время O (1) пространство. (обновление: я записал, что это действительно составляет дубликаты, но по-видимому который не верен, как продемонстрировано комментарием к другому ответу здесь).