reaper28's blog

Any approach for this question? Needed ASAP !!!!
By reaper28, history, 7 months ago, In English

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

  • Vote: I like it
  • -19
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    yes it is not from any ongoing one. its a prev year company question.

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is solution based on tries. Refer to this blog

→ Reply
»
7 months ago, # |
← Rev. 13   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply