Given an array of N elements, answer Q queries asking if there exist two elements from two specified range with a given XOR value

Question

We have array of N (≤105) elements with Q(≤105) queries.

Each query is of type: p q r s x, where we have to find if there exist a element from array in range [p,q] and an element in [r,s] whose xor is equal to X. If exists, print "true" else "false".

Constraints:

• 1 ≤ N ≤ 105
• 1 ≤ p,q,r,s ≤ N
• 1 ≤ A[i] ≤ 105

Example:

• Array: 1 2 3 4 5 6
• Query: 1 3 4 6 5
• Output: true.

1 from range [1,3] and 4 from range [4,6] has an XOR value equal to X=5.

I tried to solve it by loading the second sub array into a hashmap then XORing x with each element from first array and if the result exists in hashmap answer is yes.

But this O(n) solution for each query isn't sufficient to pass. I am looking for ideas for how I can achieve this in possible O(log n) or O(1) time for each query, or if it is possible to answer queries offline using MO's algorithm in O(√n) time.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
int a[100001];
bool query(int p,int q,int r,int s,int x)
{
 unordered_map<int,int> mp;
 for(int i =r;i<=s;i++)
 {
 mp[a[i]]=1;
 }
 for(int i =p;i<=q;i++)
 {
 if(mp.count(a[i]^x) > 0)
 {
 return true;
 }
 }
 return false;
}
int main()
{
 int n,q;
 cin>>n>>q;
 for(int i =0;i<n;i++)
 {
 cin>>a[i];
 }
 while(q--)
 {
 int p,q,r,s,x;
 cin>>p>>q>>r>>s>>x;
 // -1 because they are 1-indexed
 if(query(p-1,q-1,r-1,s-1,x))
 {
 cout<<"true\n";
 }
 else
 {
 cout<<"false\n";
 }
 }
 return 0;
}

• RE60K: Apparently I misunderstood the question that we need to check if xor of the given ranges is required, but instead a element from both ranges is required
• Alexa yuki: That means i couldn't explain the problem well enough, what would you suggest i should edit in the post to make it more obvious?
• Deduplicator: Is the array guaranteed ordered? Or even guaranteed contiguous?
• Alexa yuki: array elements can be in any order, p,q,r,s are in range [1,N], but they do not overlap. and array elements are <= 10^5. I will update the statement with this info. sorry i missed out
• vnp: Can you share a link to the problem statement, just in case?

Answer 1

1. Avoid non-standard headers. Especially giant composite-headers like <bits/stdc++.h>. They make your program unportable and/or slow compilation down.

2. You are using using namespace std;.
   That's a bad idea, read "Why is "using namespace std;" considered bad practice?".

3. Aside from its obscuring impact if you ever used the typedefs, vi and ll are unused. Remove to minimize confusion.

4. Do you know std::unordered_set? That's better for representing a set than std::unordered_map...
   Anyway, you should change the algorithm but we'll get there later.

5. You should consider whether swapping the ranges can speed things up.

6. The conditional operator (ternary operator, exp ? true_exp : false_epp) is perfect for choosing the value to use.

7. You never check for input-failure or inputs being out-of-range.

Now the algorithm:

Consider initializing a std::unordered_multimap, or if duplicates are plentiful a std::unordered_map of sorted std::vector from the input-array.
Then for each query check every element in the smaller range whether element xor x is in the whole array, and filter that down to the second range.

• Alexa yuki: 1 - 2.) I am aware of that, but at the moment i only wish to have a good algorithm for it. So this is my throw away code, you can say. 3.) those are some things i use very often, so are part of my basic template. 4. ) i choose unordered_map for easy (and efficient) look ups. and yes Algorithm needs changing. 5.) In worst case, the running time would still be O(N). 6) Ok. 7) It is guaranteed to follow the given constraints.
• Alexa yuki: Algorithm part is almost same as i have implemented already. Which happens to be too slow :(.
• Deduplicator: Hm, we are Code Review, expect everything to be reviewed. Better lean it up before submitting here. Well, you are using the map as a set, so use a set. Yes, swapping the ranges does not change the algorithms asymptotic complexity, but every little bit might help. You know trust but verify? Or at least add a comment "Input is assumed well-formed". The changed algorithm only builds the structures for lookup once, which gets amortized over all queries. Should drop the complexity from O((range_1 + range_2) * lookup) to O(min(range_1, range_2) * lookup) (lookup depends on #unique)
• Toby Speight: I felt your description of the better algorithm was a bit terse, so I've expanded on that in an answer of my own. Thanks for the inspiration.

Answer 2

Besides what Deduplicator said, some comments:

1. The easiest way to get the sets is constructing them directly from the ranges:

    std::vector<int> data;
    auto start = std::next(data.begin(), offset1);
    auto end = std::next(data.begin(), offset2);
    std::set<int> range(start, end);
   

   That way you only have to deal with the considerably smaller subsets of the vectors.

2. If you have a deterministic range do not use while loops. That's what for loops are for.

• Alexa yuki: 1. The overall complexity would still be the same, if not better :(
• Toby Speight: The other advantage of constructing the set from iterators is that (given the iterators represent a sized range) the constructor can perform the reserve() that's missing from OP code.

Answer 3

Check for invalid input:

int n,q;
 cin>>n>>q;
 for(int i =0;i<n;i++)
 {
 cin>>a[i];
 }

Input can fail, your code doesn't check for it. The least you can do is:

if (!std::cin) {
 // Fail
}

Use a code formatter:

The formatting is all over the place. Consider using clang-format, Astyle, or GNU Indent to automatically format the code.

Use meaningful identifiers:

int n,q;
 cin>>n>>q;
 for(int i =0;i<n;i++)
 {
 cin>>a[i];
 }
 while(q--)
 {
 int p,q,r,s,x;

All these single-letter identifiers make no sense to me.

Okay, I see that the specification uses them, but my comments are still valid, especially for the n and the outer q.

Simplify:

We don't need to write the words "true" and "false" in the code:

#if 0
if(query(p-1,q-1,r-1,s-1,x))
 {
 cout<<"true\n";
 }
 else
 {
 cout<<"false\n";
 }
#else
std::cout << std::boolalpha << query(p-1,q-1,r-1,s-1,x) << '\n';

Prefer EXIT_SUCCESS and EXIT_FAILURE from cstdlib to integers:

return 0 is ok. But in C and C++, that is the default behaviour, and can be elided.

But if you're going to use add the return statement, consider using the standard error codes instead of naked numbers like 0, 1, -1 et cetera.

Answer 4

It's great that you separated the program into a main() that handles the I/O and a query() function that processes a singe query. That makes it much easier to unit-test and benchmark the function. But having done so, don't throw away these tests! Keep them around (perhaps using #ifdef blocks) so reviewers/maintainers can re-use them.

---

The global variable a is best avoided. I recommend you read the input array into a std::vector and then pass a reference to that vector as one of the query arguments. Or make it a member of a structure, of which check() could be a member function.

---

The use of int for values that may be larger than 32767 is risky, as that's the minimum guaranteed value that can be represented in that type. Use a more appropriate type for the values and indexes, since the problem statement says they may be as large as 100000.

---

Avoid shadowing variables in near-ancestor scope:

while(q--)
{
 int p,q,r,s,x;

Having two different q variables makes this code harder to comprehend.

---

As you observed, the naive approach scales poorly. It doesn't help that we build a map object, incurring memory allocation/deallocation for every query.

Since we have one input array that's common to all the queries, it's worth spending some time turning it into a form that makes the queries faster to answer.

The most suitable approach here is to construct a reverse mapping which, given a particular value, can tell us which positions in the array contain that value.

That looks like this, and scales as O(n):

class tester
{
 std::vector<unsigned> values;
 // map each value to the positions where it appears
 // invariant: each vector contains indices in ascending order
 std::unordered_map<unsigned, std::vector<std::size_t>> index = {};
public:
 explicit tester(std::vector<unsigned> inputs)
 : values{std::move(inputs)}
 {
 for (unsigned i = 0; auto v: values) {
 index[v].push_back(i++);
 }
 }
};

With that available, each query is simplified. For each value in the first subrange, xor it with x to give a target value, then look up in the index whether any instances of the target lie within [r,s].

 bool operator()(std::size_t p, std::size_t q,
 std::size_t r, std::size_t s,
 unsigned x) const
 {
 // Inputs are 1-based and inclusive, so adjust lower end
 --p; --r;
 for (auto i = p; i < q; ++i) {
 auto target = values[i] ^ x;
 if (auto it = index.find(target); it != index.end()) {
 // does this vector contain any values between r and s?
 auto const& positions = it->second;
 auto least = std::ranges::lower_bound(positions, r);
 if (least != positions.end() && *least < s) {
 // yes
 return true;
 }
 }
 }
 return false;
 }

We should be able to see that since we have a O(q-p) loop which does O(log n) binary search each iteration, this scales as O((q-p)·log n).

---

Replacement code

The original had so many problems (see other answer) that it was better to rewrite from scratch. I also included a couple of easy optimisations and range checking that I omitted from the expository versions of the functions above.

This compiles cleanly, but has not been tested due to lack of suitable input file.

#include <algorithm>
#include <ranges>
#include <unordered_map>
#include <utility>
#include <vector>
class tester
{
 std::vector<unsigned> values;
 // map each value to the positions where it appears
 // invariant: each vector contains indices in ascending order
 std::unordered_map<unsigned, std::vector<std::size_t>> index = {};
public:
 explicit constexpr tester(std::vector<unsigned> inputs)
 : values{std::move(inputs)}
 {
 index.reserve(values.size());
 for (unsigned i = 0; auto v: values) {
 index[v].push_back(i++);
 }
 }
 [[nodiscard]] constexpr bool operator()(std::size_t p, std::size_t q,
 std::size_t r, std::size_t s,
 unsigned x) const
 {
 auto const size = values.size();
 // Convert intervals from 1-based inclusive to 0-based half-open
 // and fix their bounds
 p = std::clamp(p, 1uz, size+1) - 1;
 r = std::clamp(r, 1uz, size+1) - 1;
 q = std::clamp(q, 1uz, size);
 s = std::clamp(s, 1uz, size);
 if (p >= q || r >= s) {
 // empty range
 return false;
 }
 // ensure that [p,q) is the smaller range
 if (q - p > s - r) {
 std::swap(p, r);
 std::swap(q, s);
 }
 for (auto i = p; i < q; ++i) {
 auto target = values[i] ^ x;
 if (auto it = index.find(target); it != index.end()) {
 // does this vector contain any values between r and s?
 auto const& positions = it->second;
 auto least = std::ranges::lower_bound(positions, r);
 if (least != positions.end() && *least < s) {
 return true;
 }
 }
 }
 return false;
 }
};
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <ranges>
int main()
{
 std::size_t array_size, query_count;
 std::cin >> array_size >> query_count;
 if (!std::cin) {
 std::cerr << "Invalid input\n";
 return EXIT_FAILURE;
 }
 std::vector<unsigned> numbers;
 numbers.reserve(array_size);
 std::copy_n(std::istream_iterator<unsigned>(std::cin),
 array_size, std::back_inserter(numbers));
 if (!std::cin) {
 std::cerr << "Invalid input\n";
 return EXIT_FAILURE;
 }
 tester test{std::move(numbers)};
 std::cout << std::boolalpha;
 for (auto _: std::views::iota(0uz, query_count)) {
 int p, q, r, s, x; // as used in problem description
 std::cin >> p >> q >> r >> s >> x;
 if (!std::cin) {
 std::cerr << "Invalid input\n";
 return EXIT_FAILURE;
 }
 std::cout << test(p, q, r, s, x);
 }
}

I tested this against a stress case query where the array contains an ascending sequence of values (using std::ranges::iota) with a query that matches no elements (1, 0xFFFF, 1, 0xFFFF, 0x10000u).

#include <cassert>
#include <chrono>
#include <iostream>
#include <locale>
#include <numeric>
int main()
{
 std::wcout.imbue(std::locale{"en_US.UTF8"});
 using clock = std::chrono::steady_clock;
 std::vector<unsigned> numbers(100000, 0u);
 std::ranges::iota(numbers, 1);
 auto t1 = clock::now();
 auto test = tester{std::move(numbers)};
 auto t2 = clock::now();
 assert(!test(1, 0xFFFF, 1, 0xFFFF, 0x10000u));
 auto t3 = clock::now();
 std::wcout << "Setup time: " << (t2 - t1)
 << "\nQuery time: " << (t3 - t2)
 << '\n';
}

This was compiled using g++ -O3.

My results:

Setup time: 8,912,967ns
Query time: 783,308ns

Original code:

Setup time: 65ns
Query time: 6,718,516ns

When there are many queries, the setup time is amortised across them, and the query time determines the overall performance. This algorithm therefore improves the run time by almost an order of magnitude.