обзор теста codility - pair_sum_even_count

Question

Я недавно прошел онлайн-тест на codility как часть процесса найма. Мне дали две простые задачи, которые нужно решить за 1 час. Для тех, кто не знает кодов, это сайт для онлайн-тестирования кода, где вы можете решать проблемы стиля ACM на многих языках.

Если у вас 30 минут или около того, отметьте это http://codility.com/demo/run/

Моим оружием выбора обычно является Java.

Итак, одна из проблем, с которыми я столкнулся, заключается в следующем (я постараюсь вспомнить, должен был сделать снимок экрана)

Допустим, у вас есть массив A [0] = 1 A [1] = - 1 .... A [n] = x

Тогда какой самый разумный способ узнать, сколько раз A [i] + A [j] даже там, где i

Так что, если у нас есть {1,2,3,4,5} у нас есть 1 + 3 1 + 5 2 + 4 3 + 5 = 4 пары, которые даже

Код, который я написал, был похож на

int sum=0;
for(int i=0;i<A.length-1;i++){
 for (int j=i+1;j<A.length;j++){
   if( ((A[i]+A[j])%2) == 0 && i<j) {
       sum++;
    }
  }
}

Было еще одно ограничение: если количество пар больше 1e9, то оно должно быть повторено -1, но давайте забудем об этом.

Можете ли вы предложить лучшее решение для этого. Количество элементов не будет превышать 1e9 в обычных случаях.

Мне кажется, я получил 27 очков за приведенный выше код (т.е. он не идеален). Codility дает подробную оценку того, что пошло не так, у меня сейчас этого нет.

Answer 1

Сумма двух целых чисел четна тогда и только тогда, когда они либо четные, либо оба нечетные.Вы можете просто пройти через массив и сосчитать четные и вероятные.Количество возможностей объединить k чисел из набора размеров N равно N!/ ((N - k)! · K!) .Вам просто нужно указать число четных / шансов как N и 2 как k .Для этого вышеприведенное упрощается до (N · (N - 1)) / 2 .Все условие i < j состоит в том, чтобы указать, что каждая комбинация считается только один раз.

Answer 2

Вы можете найти сумму без расчета каждой пары в отдельности.

A[i]+A[j] - четное , если A [i] четное, а A [j] четное ; или A [i] нечетно, а A [j] нечетно .

Текущее общее количество нечетных и четных чисел до j можно сохранить и добавить к сумме в зависимости от того, является ли A [j] нечетным или четным :

int sum = 0;

int odd = 0;
int even = 0;
for(int j = 0; j < A.length; j++) {
    if(A[j] % 2 == 0) {
        sum += even;
        even++;
    } else {
        sum += odd;
        odd++;
    }
}

Edit:

Если вы посмотрите на A={1,2,3,4,5}, каждое значение j добавит количество пар с A[j] в качестве второго числа.

Even values:
A[j]=2 - sum += 0
A[j]=4 - sum += 1 - [2+4]

Odd values:
A[j]=1 - sum += 0
A[j]=3 - sum += 1 - [1+3]
A[j]=5 - sum += 2 - [1+5, 3+5]

Answer 3

Пожалуйста, отметьте это

if (A == null || A.length < 2) {
  return 0;
}

int evenNumbersCount = 0;
int oddNumberCount = 0;

for (int aA : A) {
  if (aA % 2 == 0) {
    evenNumbersCount++;
  } else {
    oddNumberCount++;
  }
}

int i = (evenNumbersCount * (evenNumbersCount - 1)) / 2 + (oddNumberCount * (oddNumberCount - 1)) / 2;
return i > 1000000000 ? -1 : i;

Если у кого-то есть проблемы с пониманием того, что сказал Санте, вот другое объяснение: Только нечетное + нечетное и четное + четное дает четное. Вы должны узнать, сколько там четных и нечетных чисел. Когда у вас это есть, представьте, что это проблема со встречей. Сколько людей не совпадают пары в списке нечетных чисел и четных номеров. Это та же проблема, что и то, сколько пар скажет друг другу привет на вечеринке. Это также количество ребер в полном графе. Ответ n * (n-1) / 2, потому что есть n человек, и вам нужно пожать руку людям n-1 и разделить на 2, потому что другой человек не может считать ваш коктейль отличным. Поскольку у вас есть две отдельные «партии», вы должны считать их независимо.

Answer 4

Это очень просто. Сначала вам нужно найти количество шансов и четное число в коллекции.например.x нечетно, если x & 1 == 1, даже в противном случае, если у вас есть это, зная, что добавив два четных или два коэффициента к каждому, вы получите четное.Вам необходимо вычислить сумму комбинаций двух элементов из четных и нечетных чисел.

, имеющих int A [] = {1,2,3,4,5};

int odds=0, evens=0;
for (int i=0; i< A.length; ++i)
{
if (A[i]&1==1) odds++;
else evens++;
}
return odds*(odds-1)/2 + evens*(evens-1)/2;  

// Вышесказанное вытекает из того факта, что количество возможностей объединить k чисел из набора размера N равно N!/ ((N - k)! · K!).Для k = 2 это упрощается до (N · (N - 1)) / 2

Answer 5

public int getEvenSumPairs(int[] array){

    int even=0;
    int odd=0;
    int evenSum=0;

     for(int j=0; j<array.length; ++j){

           if(array[j]%2==0) even++;
           else odd++;
     }
     evenSum=((even*(even-1)/2) + (odd *(odd-1)/2) ;
     return evenSum;
}

Answer 6

См. Также этот ответ

int returnNumOFOddEvenSum(int [] A){
    int sumOdd=0;
    int sumEven=0;

    if(A.length==0)
        return 0;

    for(int i=0; i<A.length; i++)
    {
        if(A[i]%2==0)
            sumEven++;
        else
            sumOdd++;
    }
    return factSum(sumEven)+factSum(sumOdd);
}

int factSum(int num){
    int sum=0;
    for(int i=1; i<=num-1; i++)
    {
        sum+=i;
    }
    return sum;
}

Answer 7

Это какое-то питоническое решение

x = [1,3,56,4,3,2,0,6,78,90]

def solution(x):
    sumadjacent = [x[i]+x[i+1] for i in range(len(x)-1) if x[i] < x[i+1]]
    evenpairslist = [ True for j in sumadjacent if j%2==0]
    return evenpairslist

if __name__=="__main__":
    result=solution(x)
    print(len(result))

Answer 8

Пусть считать нечетные числа как n1 и считать четные числа как n2 .

Сумма Pair(x,y) является четной, только если мы выберем оба x и y из набора четных чисел или оба x и y из нечетного набора (выбор x из четного набора и y из нечетного набора или наоборот всегда приведет к сумме пары вбыть нечетным числом).

Таким образом, общая комбинация такова, что сумма каждой пары четна = n1C2 + n2C2.

= (n1!) / ((n1-2)! * 2!) + (n2!) / ((n2-2)! * 2!)  
= (n1 * (n1 - 1)) / 2 + (n2 * (n2 - 1)) / 2 

--- Уравнение 1.
Например: пусть массив будет иметь вид: {1,2,3,4,5}
число четных чисел = n1 = 2
числонечетных чисел = n2 = 2

Итого пара, сумма пары которой четна из уравнения: 1 = (2*1)/2 + (3*2)/2 = 4 и пары: (1,3), (1,5), (2,4), (3,5).
По традиционному подходудобавление, а затем проверка могут привести к целочисленному переполнению в программировании как на положительных, так и на отрицательных крайностях.

Answer 9

Вы можете избавиться от оператора if / else и просто получить следующее:

int pair_sum_v2( int A[], int N ) {
int totals[2] = { 0, 0 };

for (int i = 0; i < N; i++ ) {
    totals[ A[i] & 0x01 ]++;
    }

return ( totals[0] * (totals[0]-1) + totals[1] * (totals[1]-1) ) / 2;
}

Answer 10

Алгоритмы скучны, вот решение на python.

>>> A = range(5)
>>> A
[0, 1, 2, 3, 4]
>>> even = lambda n: n % 2 == 0
>>> [(i, j) for i in A for j in A[i+1:] if even(i+j)]
[(0, 2), (0, 4), (1, 3), (2, 4)]

Я попробую другое решение, используя vim.