Блог пользователя reaper28

Any approach for this question? Needed ASAP !!!!
Автор reaper28, история, 7 месяцев назад, По-английски

Given an array A of N positive numbers and an integer P. Let NumPairs, be the number of pairs of elements of array A, such that their bitwise xor equal to X. You need to find the largest X, such that NumPairsx is greater or equal to P. If no such X exists print -1. Constraints:

N <=10 pow 4 P <=10 pow 9 Ai <=10 pow 9

Example:

A [1,12,13,14], P=1

QUESTION IS FROM PREVIOUS YEAR COMPANY QUESTIONS NOT FROM ANY ONGOING CONTEST

  • Проголосовать: нравится
  • -19
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by reaper28 (previous revision, new revision, compare).

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

hmmm very normal title, surely it isn't from an on-going coding test, right?

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by reaper28 (previous revision, new revision, compare).

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There is solution based on tries. Refer to this blog

→ Ответить
»
7 месяцев назад, # |
← Rev. 13   Проголосовать: нравится +10 Проголосовать: не нравится

Since N goes only up to 10^4, I imagine you can simply find all possible pairs of elements in the array and count NumPairs for all possible values of X. Something like...

int countPairs(vector<int> A, int P) {
    unordered_map<int, int> cnts;
    for(int i = 0; i < A.size() - 1; i ++)  {
        for(int j = i + 1; j < A.size(); j ++) {
            cnts[A[i] ^ A[j]] ++;
        }
    }
    int maxV = -1;
    for(auto&[X, cnt]: cnts) {
        if(cnt >= P) {
            maxV = max(maxV, X);
        }
    }
    return maxV;
}

Should suffice.

→ Ответить
  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You should probably put all of the values into an array and then sort it as unordered map has a relatively large memory constant in addition to its large time complexity constant (it performs a bit better than std::map which is notoriously slow). However I still think that sorting the array is a bit too slow, albeit faster than using map or unordered map.

    → Ответить
    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Do you mean use coordinate compression to reduce down the complexity to N^2 log N^2? If so, then you're absolutely correct, that would probably speed up the algorithm, although in retrospect I do realize that O(10^9~) would probably not fly. I suppose one could trade off the incredibly massive space complexity (of creating an array of size 10^9) for an equally unacceptable time complexity for this problem, but I guess OP should look for a better solution realistically. I think he could solve this with bitmasking and a trie, although I do not have a specific solution in mind.

      → Ответить