XOR больше 4 четно-четной или нечетной нечетной пары - PullRequest
Новая
       6

XOR больше 4 четно-четной или нечетной нечетной пары

0 голосов
/ 10 сентября 2018

Учитывая массив четных и нечетных чисел, я хочу получить количество (четно-четных) и (нечетно-нечетных) пар, XOR которых больше или равен 4. Я пробовал это с кодом ниже, но это работает в O (n ^ 2), (yikes). Кто-нибудь может предложить способ оптимизации? 

n = int(raw_input()) #array size

ar = map(int, raw_input().split()) #the array

cnt = 0

for i in xrange(len(ar)):

    for j in xrange(i+1, len(ar)):

        if ar[i] ^ ar[j] >= 4 and (not ar[i] & 1  and not ar[j] & 1):

            cnt += 1; #print ar[i],ar[j],ar[i]^ar[j];

        elif ar[i] ^ ar[j] >= 4 and (ar[i] & 1 and ar[j] & 1):

            cnt += 1
print cnt

РЕДАКТИРОВАТЬ: Я обнаружил что-то. любое число x, которое дает остаток после% 4, т.е. x% 4! = 0, приведет к 2, если XOR присвоено самому числу -2. Например, 6. Он не делится на 4, поэтому 6 XOR 6-2 (4), ==> 2. 10 не делится на 4, следовательно, 10 XOR 10-2 (8) ==> 2. Подскажите, пожалуйста, как это могло бы помочь мне оптимизировать мой код? Теперь я просто знаю, что я просто буду искать числа, кратные 4, и найду число их + 2.

Ответы [ 3 ]

0 голосов
/ 10 сентября 2018 
def xor_sum(lst)
    even_dict = a dictionary with keys being all even numbers of lst and values being their frequencies
    odd_dict = a dictionary with keys being all odd numbers of lst and values being their frequencies
    total_even_freq = sum of all frequencies of even numbers
    total_odd_freq = sum of all frequencies of odd numbers 
    even_res = process(even_dict, total_even_freq)
    odd_res = process(odd_dict, total_odd_freq)
    return even_res + odd_res

def process(dict, total_freq)
    res = 0
    for num in dict.keys
        # LSB of XOR of 2 even numbers is always 0
        # Let p = XOR of 2 even numbers; if p < 4 then p = 00000000 (minus_2) or 00000010 (plus_2)
        plus_2 = num+2
        minus_2 = num-2
        count = 0
        if( (plus_2 XOR num) < 4 and (plus_2 is a key of dict) )
            count = count + frequency_of_plus_2
        if( (minus_2 XOR num) < 4 and (minus_2 is a key of dict) )
            count = count + frequency_of_minus_2
        count = count + num
        res = res + (total_freq+1-count)
    return res

Сложность:
Предполагая, что у вас есть хороший hash function для вашего dictionaries (hashmap), средняя сложность времени составляет O(n)

0 голосов
/ 10 сентября 2018

Для простоты предположим, что в массиве нет дубликатов. Чтобы XOR между 2 числами был> = 4, они должны иметь любой другой бит (исключая младшие 2 бита). Учитывая, что мы уже знаем, что они являются четно-четными или нечетно-нечетными парами, их младший бит одинаков.

Обратите внимание, что для любого числа X X XOR (X + 4 + k) всегда будет> = 4. Таким образом, проблема заключается в рассмотрении того, что происходит с X XOR (X + 1), X XOR (X + 2) и X XOR (X + 3). X XOR (X + 1) будет> = 4, когда третий младший бит изменился, добавив только 1. Это означает, что у нас было X, заканчивающееся на 011, поэтому X + 1 заканчивается на 100, или у нас было X, заканчивающееся на 111, так что X + 1 заканчивается на 000. В обоих случаях это означает X% 4 = 3. В любом другом случае (X% 4! = 3) X XOR (X + 1) будет <4. </p>

Чтобы X XOR (X + 2) было> = 4, третий младший бит изменился путем добавления 2. Это означает, что X закончился в 011, 010, 111 или 110. Таким образом, теперь у нас есть X% 4 = 3 или X% 4 = 2.

Чтобы X Xor (X + 3) было> = 4, третий младший бит изменился путем добавления 3. Это означает, что X закончился в 011, 010, 001, 111, 110, 101. Итак, теперь у нас есть X % 4 = 3, X% 4 = 2 или X% 4 = 1.

Вот псевдокод: 

for each element in array:
    count[element] += 1
    total += 1
for each X in sorted keys of count:
    if X % 4 == 3:
        answer += count[X + 1] + count[X + 2] + count[X + 3]
    if X % 4 == 2:
        answer += count[X + 2] + count[X + 3]
    if X % 4 == 1:
        answer += count[X + 3]
    total -= count[X]
    answer += total - (count[X + 1] + count[X + 2] + count[X + 3]) # all X + 4 + K work

Чтобы учесть дубликаты, нам нужно избегать подсчета числа против самого себя. Вам нужно будет вести подсчет каждого числа и делать то же, что и выше, с модификацией, что ответом будет подсчет этого числа * (все остальные - количество чисел X + 2)

0 голосов
/ 10 сентября 2018

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

import random 
from operator import xor
import itertools

random.seed(10)

in_values = [random.randint(0, 10) for _ in range(100)]

def get_pairs_by(condition, values):
  odds  = set(filter(lambda x: x % 2 == 0, values))
  evens = set(filter(lambda x: x % 2 == 1, values))
  def filter_pairs_by_condition(values):
    return (
      (x, y) for x, y in set(
        map(lambda x: tuple(sorted(x)), 
            itertools.product(iter(values), iter(values)))) 
        if condition(xor(x, y))
      )
  return list(
    itertools.chain.from_iterable( 
      (filter_pairs_by_condition(x) for x in (odds, evens))
      )
    )


print(get_pairs_by(lambda x: x >= 4, in_values))

Ключевой момент: 

set(map(lambda x: tuple(sorted(x)), 
    itertools.product(iter(values), iter(values)))))

Что мы делаем, так это то, что пары (5, 7) и (7, 5) должны оцениваться как одинаковые, поэтому мы избавимся от них там.

Здесь у вас есть живой пример

РЕДАКТИРОВАТЬ: В качестве быстрого обновления вашего кода, вы можете использовать словарь для запоминания ранее вычисленных пар, следовательно: 

n = int(raw_input()) #array size

ar = map(int, raw_input().split()) #the array

cnt = 0

prev_computed = {}

for i in xrange(len(ar)):

    for j in xrange(i+1, len(ar)):
        if any(x in prev_compued for x in ((ar[i], ar[j]), (ar[j], ar[i]))):
            cnt += 1
            continue

        if ar[i] ^ ar[j] >= 4 and (not ar[i] & 1  and not ar[j] & 1):
            cnt += 1; #print ar[i],ar[j],ar[i]^ar[j];
            prev_computed[(ar[i], ar[j])] = True
            prev_computed[(ar[j], ar[i])] = True
        elif ar[i] ^ ar[j] >= 4 and (ar[i] & 1 and ar[j] & 1):
            cnt += 1
            prev_computed[(ar[i], ar[j])] = True
            prev_computed[(ar[j], ar[i])] = True

print cnt
...