примечание: этот комментарий основан на исходном тексте вопроса (с тех пор он был исправлен)

Если вопрос поставлен в точности, как написано выше (и это не просто опечатка), и для массива размера n функция должна вернуть (True / False), если массив состоит из чисел 1 .. .n + 1,

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

Контрпример для алгоритма XOR.

(не могу опубликовать это как комментарий)

@popopome

Для a = {0, 2, 7, 5,} он возвращает true (означает, что a является перестановкой диапазона [0, 4)), но в этом случае он должен возвращать false (a, очевидно, не является перестановкой [0, 4)).

Другой пример счетчика: {0, 0, 1, 3, 5, 6, 6} - все значения находятся в диапазоне, но есть дубликаты.

Я мог неправильно реализовать идею (или тесты) popopome, поэтому вот код:

bool isperm_popopome(int m; int a[m], int m, int  n)
{
  /** O(m) in time (single pass), O(1) in space,
      no restrictions on n,
      no overflow,
      a[] may be readonly
  */
  int even_xor = 0;
  int odd_xor  = 0;

  for (int i = 0; i < m; ++i)
    {
      if (a[i] % 2 == 0) // is even
        even_xor ^= a[i];
      else
        odd_xor ^= a[i];

      const int b = i + n;
      if (b % 2 == 0)    // is even
        even_xor ^= b;
      else
        odd_xor ^= b;
    }

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

Версия C псевдокода b3

(чтобы избежать неправильного толкования псевдокода)

Пример счетчика: {1, 1, 2, 4, 6, 7, 7}.

int pow_minus_one(int power)
{
  return (power % 2 == 0) ? 1 : -1;
}

int ceil_half(int n)
{
  return n / 2 + (n % 2);
}

bool isperm_b3_3(int m; int a[m], int m, int n)
{
  /**
     O(m) in time (single pass), O(1) in space,
     doesn't use n
     possible overflow in sum
     a[] may be readonly
   */
  int altsum = 0;
  int mina = INT_MAX;
  int maxa = INT_MIN;

  for (int i = 0; i < m; ++i)
    {
      const int v = a[i] - n + 1; // [n, n+m-1] -> [1, m] to deal with n=0
      if (mina > v)
        mina = v;
      if (maxa < v)
        maxa = v;

      altsum += pow_minus_one(v) * v;
    }
  return ((maxa-mina == m-1)
          and ((pow_minus_one(mina + m-1) * ceil_half(mina + m-1)
                - pow_minus_one(mina-1) * ceil_half(mina-1)) == altsum));
}

В Python:

def ispermutation(iterable, m, n):
    """Whether iterable and the range [n, n+m) have the same elements.

       pre-condition: there are no duplicates in the iterable
    """ 
    for i, elem in enumerate(iterable):
        if not n <= elem < n+m:
            return False

    return i == m-1

print(ispermutation([1, 42], 2, 1)    == False)
print(ispermutation(range(10), 10, 0) == True)
print(ispermutation((2, 1, 3), 3, 1)  == True)
print(ispermutation((2, 1, 3), 3, 0)  == False)
print(ispermutation((2, 1, 3), 4, 1)  == False)
print(ispermutation((2, 1, 3), 2, 1)  == False)

Это O (м) во времени и O (1) в пространстве. Он не учитывает дубликаты.

Альтернативное решение:

def ispermutation(iterable, m, n): 
    """Same as above.

    pre-condition: assert(len(list(iterable)) == m)
    """
    return all(n <= elem < n+m for elem in iterable)

МОЙ ТЕКУЩИЙ ЛУЧШИЙ ВАРИАНТ

def uniqueSet( array )
  check_index = 0; 
  check_value = 0; 
  min = array[0];
  array.each_with_index{ |value,index|
         check_index = check_index ^ ( 1 << index );
         check_value = check_value ^ ( 1 << value );
         min = value if value < min
  } 
  check_index =  check_index  << min;
  return check_index == check_value; 
end

O (n) и пробел O (1)

Я написал сценарий для комбинаций грубой силы, которые могут не сработать, но он не нашел ни одного. Сообщите, если у вас есть массив, который противоречит этой функции. :)

@ J.F. Себастьян

Это не настоящий алгоритм хеширования. Технически это высокоэффективный упакованный логический массив «видимых» значений.

ci = 0, cv = 0
[5,4,3]{ 
  i = 0 
  v = 5 
  1 << 0 == 000001
  1 << 5 == 100000
  0 ^ 000001  = 000001
  0 ^ 100000  = 100000

  i = 1
  v = 4 
  1 << 1 == 000010
  1 << 4 == 010000
  000001 ^ 000010  = 000011
  100000 ^ 010000  = 110000 

  i = 2
  v = 3 
  1 << 2 == 000100
  1 << 3 == 001000
  000011 ^ 000100  = 000111
  110000 ^ 001000  = 111000 
}
min = 3 
000111 << 3 == 111000
111000 === 111000

Дело в том, что для "подделки" большинства проблемных случаев используются дубликаты. В этой системе XOR наказывает вас за использование одного и того же значения дважды и предполагает, что вы сделали это 0 раз.

Здесь, конечно же, есть предостережения:

1. длина входного массива и максимальное значение массива ограничены максимальным значением для $x в ( 1 << $x > 0 )

2. конечная эффективность зависит от того, как ваша базовая система реализует возможности:

   1. shift 1 bit n places right.
   2. xor 2 регистра. (где "регистры" могут, в зависимости от реализации, охватывать несколько регистров)

   edit Обратите внимание, приведенные выше утверждения могут сбивать с толку. Предполагая идеальную машину, где «целое число» - это регистр с бесконечной точностью, который все еще может выполнить a ^ b за время O (1).

Но, отказавшись от этих предположений, нужно начать задавать вопросы об алгоритмической сложности простой математики.

• Насколько сложен 1 == 1? Разумеется, это должно быть O (1) каждый раз, верно ?.
• А как насчет 2 ^ 32 == 2 ^ 32.
• О (1)? 2 ^ 33 == 2 ^ 33? Теперь у вас есть вопрос о размере регистра и базовой реализации.
• К счастью, XOR и == могут выполняться параллельно, поэтому, если кто-то предполагает бесконечную точность и машину, предназначенную для работы с бесконечной точностью, можно безопасно предположить, что XOR и == принимают постоянное время независимо от их значения (поскольку его бесконечная ширина, это будет иметь бесконечное заполнение 0. Очевидно, что этого не существует. Но также изменение 000000 на 000100 не увеличивает использование памяти.
• Тем не менее, на некоторых машинах (1 ‹< 32) ‹< 1 будет потреблять больше памяти, но неизвестно, сколько.

Версия C Ruby-решения Кента Фредрика

(для облегчения тестирования)

Контрпример (для версии C): {8, 33, 27, 30, 9, 2, 35, 7, 26, 32, 2, 23, 0, 13, 1, 6, 31, 3, 28, 4, 5, 18, 12, 2, 9, 14, 17, 21, 19, 22, 15, 20, 24, 11, 10, 16, 25}. Здесь n = 0, m = 35. Эта последовательность пропускает 34 и имеет два 2.

Это решение O (m) во времени и O (1) в пространстве.

Значения, выходящие за пределы допустимого диапазона, легко обнаруживаются в O (n) во времени и O (1) в пространстве, поэтому тесты сконцентрированы на последовательностях в пределах диапазона (означает, что все значения находятся в допустимом диапазоне [n, n+m)). В противном случае {1, 34} - пример счетчика (для версии C sizeof (int) == 4, стандартное двоичное представление чисел).

Основное различие между версией C и Ruby: оператор << будет вращать значения в C из-за конечного sizeof (int), но в Ruby числа будут расти, чтобы соответствовать результату, например,

Рубин: 1 << 100 # -> 1267650600228229401496703205376

C: int n = 100; 1 << n // -> 16

В Ruby: check_index ^= 1 << i; эквивалентно check_index.setbit(i). Тот же эффект можно было бы реализовать на C ++: vector<bool> v(m); v[i] = true;

bool isperm_fredric(int m; int a[m], int m, int n)
{
  /**
     O(m) in time (single pass), O(1) in space,
     no restriction on n,
     ?overflow?
     a[] may be readonly
   */
  int check_index = 0;
  int check_value = 0;

  int min = a[0];
  for (int i = 0; i < m; ++i) {

    check_index ^= 1 << i;
    check_value ^= 1 << (a[i] - n); //

    if (a[i] < min)
      min = a[i];
  }
  check_index <<= min - n; // min and n may differ e.g., 
                           //  {1, 1}: min=1, but n may be 0.
  return check_index == check_value;
}

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

bool *seen_isperm_trusted  = NULL;
bool isperm_trusted(int m; int a[m], int m, int n)
{
  /** O(m) in time, O(m) in space */

  for (int i = 0; i < m; ++i) // could be memset(s_i_t, 0, m*sizeof(*s_i_t));
    seen_isperm_trusted[i] = false;

  for (int i = 0; i < m; ++i) {

    if (a[i] < n or a[i] >= n + m)
      return false; // out of range

    if (seen_isperm_trusted[a[i]-n])
      return false; // duplicates
    else
      seen_isperm_trusted[a[i]-n] = true;
  }

  return true; // a[] is a permutation of the range: [n, n+m)
}

Входные массивы создаются с помощью:

void backtrack(int m; int a[m], int m, int nitems)
{
  /** generate all permutations with repetition for the range [0, m) */
  if (nitems == m) {
    (void)test_array(a, nitems, 0); // {0, 0}, {0, 1}, {1, 0}, {1, 1}
  }
  else for (int i = 0; i < m; ++i) {
      a[nitems] = i;
      backtrack(a, m, nitems + 1);
    }
}

Ответ от "nickf" не работает, если массив не отсортирован var_dump (testArray (array (5, 3, 1, 2, 4), 1, 5)); // дает "дубликаты" !!!!

Также ваша формула для вычисления суммы ([n ... n + m-1]) выглядит неверной .... правильная формула: (m (m + 1) / 2 - n (n-1) / 2)

Массив содержит N чисел, и вы хотите определить, суммируются ли два из этих чисел с заданным числом K. Например, если введено 8,4, 1,6 и K равно 10, ответ будет положительным (4 и 6 ). Число можно использовать дважды. Сделайте следующее. а. Приведите алгоритм O (N2) для решения этой проблемы. б. Приведите алгоритм O (N log N) для решения этой проблемы. (Подсказка: сначала отсортируйте элементы. После этого вы сможете решить задачу за линейное время.) C. Кодируйте оба решения и сравните время работы ваших алгоритмов. 4.

Произведение m последовательных чисел делится на m! [m факториал]

поэтому за один проход вы можете вычислить произведение m чисел, а также вычислить m! и посмотрим, есть ли произведение по модулю m! равен нулю в конце прохода

Возможно, я что-то упускаю, но вот что приходит мне на ум ...

что-то вроде этого в python

my_list1 = [9,5,8,7,6]

my_list2 = [3,5,4,7]

def последовательный (my_list):

count = 0
prod = fact = 1
for num in my_list:
    prod *= num
    count +=1 
    fact *= count
if not prod % fact: 
    return 1   
else:   
    return 0 

печать последовательного (my_list1)

печать последовательного (my_list2)

HotPotato ~ $ python m_consecutive.py

1

0

Предлагаю следующее:

Выберите конечный набор простых чисел P_1, P_2, ..., P_K и вычислите вхождения элементов во входной последовательности (за вычетом минимума) по модулю каждого P_i. Образец действительной последовательности известен.

Например, для последовательности из 17 элементов по модулю 2 у нас должен быть профиль: [9 8], по модулю 3: [6 6 5], по модулю 5: [4 4 3 3 3] и т. Д.

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

S_i is an int array of size P_i, initially filled with 0, i=1..K
M is the length of the input sequence
Mn = INT_MAX
Mx = INT_MIN

for x in the input sequence:
  for i in 1..K: S_i[x % P_i]++  // count occurrences mod Pi
  Mn = min(Mn,x)  // update min
  Mx = max(Mx,x)  // and max

if Mx-Mn != M-1: return False  // Check bounds

for i in 1..K:
  // Check profile mod P_i
  Q = M / P_i
  R = M % P_i
  Check S_i[(Mn+j) % P_i] is Q+1 for j=0..R-1 and Q for j=R..P_i-1
  if this test fails, return False

return True

Любой непрерывный массив [n, n + 1, ..., n + m-1] может быть отображен на «базовый» интервал [0, 1, ..., m] с помощью оператора по модулю. Для каждого i в интервале существует ровно один i% m в базовом интервале, и наоборот.

Любой непрерывный массив также имеет размер m (максимум - минимум + 1), равный его размеру.

Используя эти факты, вы можете создать «обнаруженный» логический массив того же размера, содержащий изначально все ложные данные, и при посещении входного массива установить для связанных «обнаруженных» элементов значение true.

Этот алгоритм составляет O (n) в пространстве, O (n) во времени и проверяет наличие дубликатов.

def contiguous( values )
    #initialization
    encountered = Array.new( values.size, false )
    min, max = nil, nil
    visited = 0

    values.each do |v|

        index = v % encountered.size

        if( encountered[ index ] )
            return "duplicates"; 
        end

        encountered[ index ] = true
        min = v if min == nil or v < min
        max = v if max == nil or v > max 
        visited += 1
    end

    if ( max - min + 1 != values.size ) or visited != values.size
        return "hole"
    else
        return "contiguous"
    end

end

tests = [ 
[ false, [ 2,4,5,6 ] ], 
[ false, [ 10,11,13,14 ] ] , 
[ true , [ 20,21,22,23 ] ] , 
[ true , [ 19,20,21,22,23 ] ] ,
[ true , [ 20,21,22,23,24 ] ] ,
[ false, [ 20,21,22,23,24+5 ] ] ,
[ false, [ 2,2,3,4,5 ] ]
]

tests.each do |t|
    result = contiguous( t[1] )
    if( t[0] != ( result == "contiguous" ) )
        puts "Failed Test : " + t[1].to_s + " returned " + result
    end
end

Мне нравится идея Грега Хьюгилла о сортировке Radix. Чтобы найти дубликаты, вы можете выполнить сортировку за время O (N) с учетом ограничений на значения в этом массиве.

Для временного интервала O (1) O (N) на месте, который восстанавливает исходный порядок списка, вам не нужно выполнять фактическую замену этого числа; можно просто пометить его флажком:

//Java: assumes all numbers in arr > 1
boolean checkArrayConsecutiveRange(int[] arr) {

// find min/max
int min = arr[0]; int max = arr[0]
for (int i=1; i<arr.length; i++) {
    min = (arr[i] < min ? arr[i] : min);
    max = (arr[i] > max ? arr[i] : max);
}
if (max-min != arr.length) return false;

// flag and check
boolean ret = true;
for (int i=0; i<arr.length; i++) {
    int targetI = Math.abs(arr[i])-min;
    if (arr[targetI] < 0) {
        ret = false; 
        break;
    }
    arr[targetI] = -arr[targetI];
}
for (int i=0; i<arr.length; i++) {
    arr[i] = Math.abs(arr[i]);
}

return ret;
}

Хранение флагов внутри данного массива является своего рода обманом и плохо сочетается с распараллеливанием. Я все еще пытаюсь придумать способ сделать это, не касаясь массива за время O (N) и пространство O (log N). Проверка по сумме и по сумме наименьших квадратов (arr [i] - arr.length / 2.0) ^ 2 кажется, что это может сработать. Одна определяющая характеристика, которую мы знаем о массиве 0 ... m без дубликатов, заключается в том, что он равномерно распределен; мы должны просто проверить это.

Вот если бы я только мог это доказать.

Я хотел бы отметить, что приведенное выше решение с использованием факториала занимает пространство O (N) для хранения самого факториала. N! > 2 ^ N, для хранения которого требуется N байтов.

Ой! Я застрял в повторяющемся вопросе и не увидел здесь уже идентичных решений. И я подумал, что наконец-то сделал что-то оригинальное! Вот исторический архив того времени, когда я был немного больше доволен:

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

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

Я не очень люблю псевдокод и думаю, что код может иметь больше смысла, чем слова. Вот реализация, которую я написал на PHP. Прислушайтесь к комментариям.

function is_permutation($ints) {

  /* Gather some meta-data. These scans can
     be done simultaneously */
  $lowest = min($ints);
  $length = count($ints);

  $max_index = $length - 1;

  $sort_run_count = 0;

  /* I do not have any proof that running this sort twice
     will always completely sort the array (of course only
     intentionally happening if the array is a permutation) */

  while ($sort_run_count < 2) {

    for ($i = 0; $i < $length; ++$i) {

      $dest_index = $ints[$i] - $lowest;

      if ($i == $dest_index) {
        continue;
      }

      if ($dest_index > $max_index) {
        return false;
      }

      if ($ints[$i] == $ints[$dest_index]) {
        return false;
      }

      $temp = $ints[$dest_index];
      $ints[$dest_index] = $ints[$i];
      $ints[$i] = $temp;

    }

    ++$sort_run_count;

  }

  return true;

}

Итак, есть алгоритм, который принимает O (n ^ 2), который не требует изменения входного массива и занимает постоянное пространство.

Во-первых, предположим, что вы знаете n и m. Это линейная операция, поэтому она не добавляет дополнительной сложности. Затем предположим, что существует один элемент, равный n, и один элемент, равный n+m-1, а все остальные находятся в [n, n+m). Учитывая это, мы можем свести проблему к наличию массива с элементами в [0, m).

Теперь, когда мы знаем, что элементы ограничены размером массива, мы можем рассматривать каждый элемент как узел с единственной ссылкой на другой элемент; другими словами, массив описывает ориентированный граф. В этом ориентированном графе, если нет повторяющихся элементов, каждый узел принадлежит циклу, то есть узел доступен от самого себя за m или меньше шагов. Если есть повторяющийся элемент, значит, существует один узел, который вообще недоступен для себя.

Итак, чтобы обнаружить это, вы проходите весь массив от начала до конца и определяете, возвращается ли каждый элемент сам к себе за <=m шагов. Если какой-либо элемент недостижим за <=m шагов, значит, у вас есть дубликат, и вы можете вернуть false. В противном случае, когда вы закончите посещать все элементы, вы можете вернуть true:

for (int start_index= 0; start_index<m; ++start_index)
{
    int steps= 1;
    int current_element_index= arr[start_index];
    while (steps<m+1 && current_element_index!=start_index)
    {
        current_element_index= arr[current_element_index];
        ++steps;
    }

    if (steps>m)
    {
        return false;
    }
}

return true;

Вы можете оптимизировать это, сохранив дополнительную информацию:

1. Запишите сумму продолжительности цикла для каждого элемента, если цикл не посещает элемент перед этим элементом, назовите его sum_of_steps.
2. Для каждого элемента вывести только m-sum_of_steps узлов. Если вы не вернетесь к начальному элементу и не посетите элемент перед начальным элементом, вы нашли цикл, содержащий повторяющиеся элементы, и можете вернуть false.

Это все еще O (n ^ 2), например {1, 2, 3, 0, 5, 6, 7, 4}, но это немного быстрее.

ciphwn прав. Все дело в статистике. С точки зрения статистики, возникает вопрос: образует ли последовательность чисел дискретное равномерное распределение. Дискретное равномерное распределение - это когда все значения из конечного набора возможных значений равновероятны. К счастью, есть несколько полезных формул, позволяющих определить, является ли дискретный набор однородным. Во-первых, для определения среднего значения набора (a..b) будет (a + b) / 2, а дисперсия - (n.n-1) / 12. Затем определите дисперсию данного набора:

variance = sum [i=1..n] (f(i)-mean).(f(i)-mean)/n

а затем сравните с ожидаемой дисперсией. Для этого потребуется два прохода по данным: один раз для определения среднего значения, а второй - для расчета дисперсии.

Использованная литература:

• равномерное дискретное распределение
• отклонение

Вот решение за время O (N) и дополнительное пространство O (1) для поиска дубликатов: -

public static boolean check_range(int arr[],int n,int m) {

        for(int i=0;i<m;i++) {
            arr[i] = arr[i] - n;
            if(arr[i]>=m)
                return(false);
        }

        System.out.println("In range");

        int j=0;
        while(j<m) {
            System.out.println(j);
            if(arr[j]<m) {

                if(arr[arr[j]]<m) {

                    int t = arr[arr[j]];
                    arr[arr[j]] = arr[j] + m;
                    arr[j] = t;
                    if(j==arr[j]) {

                        arr[j] = arr[j] + m;
                        j++;
                    }

                }

                else return(false);

            }

            else j++;

        }

Объяснение: -

1. Привести число в диапазон (0, m-1) с помощью arr [i] = arr [i] - n, если за пределами диапазона вернуть false.
2. для каждого я проверяю, не занят ли arr [arr [i]], то есть ли он имеет значение меньше m
3. если это так, поменяйте местами (arr [i], arr [arr [i]]) и arr [arr [i]] = arr [arr [i]] + m, чтобы указать, что он занят
4. если arr [j] = j, просто добавьте m и увеличьте j
5. если arr [arr [j]]> = m означает, что он занят, следовательно, текущее значение дублируется, следовательно, возвращается false.
6. если arr [j]> = 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 временная переменная внутри sum () и 1 переменная для текущего элемента, взятого из потока)

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

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

Fail := False;
Sum1 := 0;
Sum2 := 0;
TSum1 := 0;
TSum2 := 0;

For i := 1 to m do
  Begin
    TSum1 := TSum1 + i;
    TSum2 := TSum2 + i * i;
    Item := Array[i] - n;
    If (Item < 0) or (Item >= m) then 
      Fail := True
    Else 
      Begin
        Sum1 := Sum1 + Item;
        Sum2 := Sum2 + Item * Item;
      End;
  End;
Fail := Fail Or (Sum1 <> TSum1) or (Sum2 <> TSum2);

Устали и нет компилятора, но я думаю, что это дает время выполнения O (m) и не обманешь.

Похоже, что мы могли бы проверить наличие дубликатов, умножив все числа n ... n + m вместе, а затем сравнив это значение с ожидаемым продуктом последовательности без дубликатов m! / (N-1)! < / strong> (обратите внимание, что это предполагает, что последовательность не может пройти как тест ожидаемой суммы , так и тест ожидаемого продукта).

is_range(int[] nums, int n, int m) {
  sum_to_m := (m * (m + 1)) / 2
  expected_sum := sum_to_m - (n * (n - 1)) / 2
  real_sum := sum(nums)
  expected_product := m! / (n - 1)!
  real_product := product(nums)
  return ((real_sum == expected_sum) && (expected_product == real_product))

// low must be less than high
public boolean isSequence(int[] nums, int low, int high) {
    int shift = 1 - low;
    low += shift;
    high += shift;

    int sum = 0;
    int sumSquares = 0;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i] + shift;

        if (num < low)
            return false;
        else if (num > high)
            return false;

        sum += num;
        sumSquares += num * num;
    }

    int expectedSum = (high * (high + 1)) / 2;

    if (sum != expectedSum)
        return false;

    int expectedSumSquares = high * (high + 1) * (2 * high + 1) / 6;

    if (sumSquares != expectedSumSquares)
        return false;

    return true;
}