Что не так с этим решением? (Тест на переносимость Perm-Missing-Elem)

Похоже, вы нажимаете максимальное значение, которое может удерживать переменная PHP, когда вы выполняете умножение. Я не уверен, что PHP позволяет работать с битами, но эту проблему можно легко решить, используя что-то похожее на класс BitSet Java.

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

Вот код Java, который реализует вышеуказанную логику (также 100/100 на Codility)

 public int solution(int[] A) { long result = 0L; BitSet all_elements = new BitSet(); BitSet given_elements = new BitSet(); for (int i = 0; i < A.length; i++) { given_elements.set((int) A[i]); } for (int i = 1; i <= A.length + 1; i++) { all_elements.set(i); } all_elements.xor(given_elements); for (int i = 0; i < all_elements.length(); ++i) { if(all_elements.get(i)) { result = i; break; } } return (int)result; } 

Решение 100/100 php для PermMissingElem:

 function solution($A) { $N = count($A); $sum = ($N + 2) * ($N + 1) / 2; for($i = 0; $i < $N; $i++){ $sum -= $A[$i]; } return intval($sum); } 

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

Решение, конечно, основано на старой арифметической хитрости, чтобы добавить большой набор смежных чисел, классно отнесенный Карлу Фридриху Гаусу, который открыл его, когда он был молодым мальчиком.

OP столкнулся с проблемой с переполнением целых чисел из-за умножения, превышающего 32-битную точность для N> 65536. Вот небольшой трюк, чтобы избежать этого для данного диапазона N = [0,00,000]. При вычислении суммы всех int (сумма Гаусса) для чисел из [1..N + 1] мы вычитаем смещение (N + 2) / 2, чтобы сделать его нулевой суммой (или, самое большее, «смещением» в случай N нечетный). Аналогичным образом мы также вычитаем это смещение из всех значений в массиве. Таким образом, мы смещаем диапазон чисел, которые должны быть добавлены максимум [-50 000 … + 50 000]. В худшем случае, т. Е. Если все положительные (или отрицательные) номера диапазонов находятся в последовательности, наибольшая промежуточная сумма никогда не превышает 31 бит, поэтому переполнение не произойдет. Для чередующихся положительных и отрицательных чисел промежуточная сумма будет еще меньше.

После вычитания суммы массива из суммы Гаусса мы снова корректируем, добавляя обратно смещение, чтобы найти отсутствующий элемент массива.

Вот код на C ++ (он забил 100% в тестах на кодовость):

 int solution(vector<int> &A) { int N; int sum; int gauss; // sum of all ints in [1..N+1] using Gauss' trick int offset; // subtract offset from all numbers to make it a zero-sum int num_x; N = int(A.size()); // convert from size_t to int sum = 0; offset = (N+2) >> 1; // make range symmetric between [-N/2..N/2] to avoid integer overflow in Gauss sum for large N // "gauss" should nominally be a zero sum, but if N is odd then N/2 is truncated // and offset is off by 1/2 for each of the N elements. This formula compensates for that. gauss = (N & 1) * offset; for (int i = 0; i < N; i++) { sum += (A[i] - offset); // this is the O(n) part of summing all elements in the array } num_x = gauss - sum + offset; // find the missing number return num_x; } 

Я новичок в stackoverflow, попытался сделать форматированный путь. Вот мой ответ в java с оценкой 100/100 ……. с O (n) сложностью. Если вы хотите, вы можете увидеть его по следующей ссылке …. http://codility.com/demo/results/demoJJERZ4-E7Z/

 public int solution(int[] A) { int len = A.length; int result = 0; int[] B; B = new int[len+1]; for(int i=0; i<= B.length-1; i++) { B[i] = i+1; } // int n = len +1; int i, sum1 = 0, sum2 = 0; for (i = 0; i <= A.length-1; i++) { sum1 = sum1 + A[i]; } for (i = 0; i <= B.length-1; i++) { sum2 = sum2 + B[i]; } result = sum2 - sum1; return result; } 

Рассмотрим это решение 100/100 в Ruby:

 # Algorithm: # # * Compute theoretical sum based on array size. # * Compute actual sum. # * Subtract one from the other and you get the missing element. def solution(ar) # Trivial case. return 1 if ar.empty? size = ar.size + 1 full_sum = (size*(size + 1))/2 actual_sum = ar.inject(:+) # Result. full_sum - actual_sum end #--------------------------------------- Tests def test sets = [] sets << ["empty", 1, []] sets << ["12", 3, [1, 2]] sets << ["13", 2, [1, 3]] sets << ["sample", 4, [2, 3, 1, 5]] sets.each do |name, expected, ar| out = solution(ar) raise "FAILURE at test #{name.inspect}: #{out.inspect} != #{expected.inspect}" if out != expected end puts "SUCCESS: All tests passed" end 

Код с PHP: я получил (100%)

($ A) {

 $arraySum=0; $totalSum=0; $res = 0; for($i=0;$i<count($A);$i++) { $arraySum += $A[$i]; $totalSum += $i+1 ; } $totalSum += $i+1 ; return abs((int)($totalSum - $arraySum)) ; 

}

100/100 в Python. Всего 3 линии и легко понять.

 def solution(A): sum1 = sum(range(1,len(A)+2)) sum2 = sum(A) return sum1-sum2 

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

 def solution(A): size = 0 array_sum = 0 for item in A: size += 1 array_sum += item expected_sum = (size+1)*(size+2)/2 return expected_sum - array_sum 

Пожалуйста, просмотрите мое решение, моя сложность времени – O (N), а временная сложность – O (N), оценка – 100.

 int solution(int A[], int N) { int * p = (int *)malloc((N + 1)*sizeof(int)); memset(p, 0, (N + 1)*sizeof(int)); int i; int ret = 0; for (i = 0; i < N; i++) { A[i] = A[i] - 1; } for (i = 0; i < N; i++) { p[A[i]] = 1; } for (i = 0; i <= N; i++) { if(p[i] == 0) { ret = i + 1; break; } } free(p); return ret; 

}

Решение 100/100 Objective C для PermMissingElem:

 int solution(NSMutableArray *A) { unsigned long length = [A count] + 1; unsigned long sum1 = 0; unsigned long sum2 = 0; for (int i=0; i < [A count]; i++) { sum1 += [[A objectAtIndex:i] longValue]; } sum2 = ((((length+1)*length)/2) - sum1); return sum2; } 

Другое решение C для PermMissingElem (Scored 100/100 on Codility):

 #include <math.h> int solution(int A[], int N) { double sum = (pow(N, 2) + 3 * N + 2) / 2; int i; for (i = 0; i < N; i++) { sum -= A[i]; } return (int)sum; } 

Первый вклад когда-либо (перекрестите пальцы, чтобы сделать это правильно!). Мое решение для C ++ следующее:

 int solution(int A[], int N) { int sum = 0; for(int i=0; i<N; i++) { sum+= (i+1) - A[i]; } sum+=(N+1); return(sum); } 

Не нужно включать другие библиотеки ;-). Надеюсь, это поможет всем!

Вот мое решение. Он в основном перебирает массив, устанавливая соответствующие элементы на ноль. После обработки массива индекс ненулевого элемента указывает на недостающее значение.

 void f( vector<int> &A, int i ) { if( i != A.size()+1 && i != 0 ) { int j = A[i-1]; A[i-1] = 0; f(A, j); } } int solution(vector<int> &A) { for ( int i = 0; i < A.size(); i++) { f(A, A[i]); } for( int i = 0; i < A.size(); i++) { if(A[i] != 0) return i+1; } return A.size()+1; } 

100% Оценка: для пролетающей телеграммы в Перми

 function solution($A){ return intval(intval(((count($A)+1) * ((count($A)+1) + 1)) / 2) - intval(array_sum($A))); } 

хотя я получил только 80: (… но это сработало

 int solution(int A[], int N) { int ret, nsum, i, sum = 0; nsum=(N * (N + 1)) / 2; for(i = 0; i < N; i++){ sum = sum + A[i]; } sum = (sum - (N + 1)); ret = sum - nsum; return ret; } 

Это простое решение составляет 100%:

 int solution(int A[], int N) { // write your code in C90 double sum = N/2.; int i; double sumA=0; for(i=0; i<N; ++i) { sumA += A[i] - N/2.; } sumA -= N+1; return sum - sumA; } 

Вау, некоторые действительно хорошие ответы здесь …

Мой начальный 100% для JavaScript не был O (1) пространственной сложностью, как того требует тест:

 var ll = A.length, lookup = {}; for (i=0; i<ll; i++) lookup[A[i]] = true; for (i=0; i<ll; i++) if (!lookup[i+1]) return i+1; 

Придя сюда и увидев прекрасные должности, я выбрал код Daniel Caballero , упрощенный vaxquis, чтобы перейти на Javascript и вставить здесь для будущего удовольствия:

 var N = A.length, sum = 2*N + 1, i; for (i = N-1; i >= 0; i--) sum += (iA[i]); return sum; 

короткий ответ на C ++, оценка теста 100%

 #include<numeric> int solution(vector<int> &A) { // compute sum of all elements, needs <numeric> long long sum = std::accumulate(A.begin(), A.end(), 0); // number of elements as 64-bit int to avoid overflow for large arrays long long N = static_cast<long long>(A.size()); // missing element is sum of elems 1 to N+1 minus sum, cast to int return static_cast<int>( ((N+1)*(N+2))/2 - sum ); } 

 function solution($A) { $sum = array_sum($A); $sum2 = 0; for ($i = 1; $i <= count($A)+1; $i++) { $sum2 += $i; } return $sum2-$sum; } 

Решение php 100/100

Мое решение 100/100 в O (N) или O (N * log (N)) PHP

 function solution($A) { $right = 0; $count = count($A); $left = 0; for ($i = 0; $i < $count; $i++) { $right += $A[$i]; $left += ($i + 1); } $left += $count; return (int)(abs(($right - $left))+1); } 

Немного короче 1 Line PHP-решение 100/100 PermMissingElem:

 function solution($a) { return array_sum(range(1, count($a)+1)) - array_sum($a); } 

Мое PHP-решение для этой проблемы: оценка 100/100

 function solution($a) { $c = count($a); // counting the elements $sum = ($c + 2) * ($c + 1) / 2; // getting the elements sum $s = array_sum($A); // taking the sum of actual array elements return intval($sum - $s ); //returning the difference }//end of solution 

С наилучшими пожеланиями, надеюсь, это поможет

100/100 в PHP и гораздо более читаемая реализация n-го числа треугольника

 function solution($a) { $array_count = count($a) + 1; $sum = (($array_count + 1) * $array_count) / 2; $result = $sum - array_sum($a); return $result; } 

 int solution(int []A){ //missing number is sum of all possible entries ([1..N+1]) minus //sum of all items in A that are with the constrain [1..N+1] int N = A.length; long sum = 0L; for(int i=1;i<=N+1;i++){ sum += i; } long sumPossible= 0L; for(int i=0; i<N;i++){ int x = A[i]; boolean outOfRange = x<1 || x>N+1; if(!outOfRange) { sumPossible += x; } } return (int)(sum-sumPossible); } 

C ++ однострочное решение 100/100:

 #include <algorithm> #include <functional> int solution(vector<int> &A) { return std::accumulate(A.begin(), A.end(), (A.size()+1) * (A.size()+2) / 2, std::minus<int>()); } 

Вздох, я должен признать, что это весело … сумма N + 1 целых чисел = (N + 1) (N + 2) / 2 = N [(N + 2) / 2] + (N + 2) / 2 = N * factor + factor, где factor = (N + 2) / 2.

оценка 100/100 Сложность: O (N) или O (N * log (N))

 int solution(int A[], int N) { int factor = N+2; int total = factor; for (int i=0;i<N;i++){ total += (factor - (A[i]<<1)); } return (total>>1)+(total&1); } 

Это мое решение для PHP:

 function solution($A) { $n = count($A) + 1; return (($n * ($n + 1)) / 2) - (array_sum($A)); } 

 public static int solution(int[] A) { int Min = A.Min(); int Max = A.Max(); for (int i = Min; i < Max; i++) { if (A.Where(t => t == Min+i).ToArray().Length == 0) { return Min+i; } } return Min-1; }