Member Avatar for arushi.05

any one knows how to write this program:-

given two arrays A and B . array 'A' contains all the elements of 'B' but one more element extra. write a c++ function which accepts array 'A' and 'B' and its size as arguments/parameters and find out the extra element in array A.(restriction:-array elemts are not in order).

help me if you know the answer...............

  • 3 Contributors
  • 2 Replies
  • 139 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by Despairy

Dani AI

Generated

Short answer for : use an O(n) scan. Two safe, practical options follow — pick one based on element type.

If the arrays hold integer values (any duplicates allowed), the XOR trick is simplest and uses O(1) extra memory. It works because every value that appears in both arrays cancels out under XOR, leaving the extra element.

int findExtraXor(const int* A, size_t sizeA, const int* B, size_t sizeB) {
    unsigned int acc = 0;
    for (size_t i = 0; i < sizeA; ++i) acc ^= static_cast<unsigned int>(A[i]);
    for (size_t i = 0; i < sizeB; ++i) acc ^= static_cast<unsigned int>(B[i]);
    return static_cast<int>(acc);
}

Caveats: use an unsigned type sized big enough for your values (uint64_t if needed). XOR only makes sense for integer-like types. It still works if the extra value appears elsewhere as long as counts differ by one.

If elements are non-integer (strings, structs) or you need robustness, use a frequency map. This is O(n) time and O(n) extra memory but handles any hashable type and avoids bitwise assumptions.

template<typename T>
T findExtraHash(const std::vector<T>& A, const std::vector<T>& B) {
    std::unordered_map<T,int> cnt;
    for (const auto &v : B) ++cnt[v];
    for (const auto &v : A) {
        auto it = cnt.find(v);
        if (it == cnt.end() || it->second == 0) return v;
        --it->second;
    }
    throw std::runtime_error("No extra element found");
}

Notes: avoid the naive sum-difference approach when values or counts can overflow. Sorting both arrays and scanning is an alternative (O(n log n), O(1) extra if done in-place). As and hinted, O(n) is possible — choose XOR for speed/space with integers, or the hash/count method for general types.

Recommended Answers

All 2 Replies

Member Avatar for WaltP

I do...

If you want help, you have to provide the work, we can provide direction and suggestions.

Member Avatar for Despairy

O( n ) right waltP? just checking ;)
arushi when you show us some work we'll help you with the best answer there is,
and you will learn stuff - AWESOMEEEEEEEE

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.