Find All Duplicates in an Array using XOR method c++

Question

Q. Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space

My code

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {   
        
        vector<int> final;
        int ans=0;
        
        // XOR n ke liye
        for(int i=0;i<nums.size();i++)
        {
            ans=ans^nums[i];
        }
        final.push_back(ans);
    
        // XOR n-1 ke liye
        for(int i=1;i<nums.size();i++)
        {
            ans=ans^i;
        }
        final.push_back(ans);
        return final;
    }
};

Input - [4,3,2,7,8,2,3,1]

Desired Output - [2,3]

My output - [10,10]

please do not spam tags. THis isnt C, i see no sorting and neither a hashmap — 463035818_is_not_an_ai, Aug 09 '22 at 11:43
what is your question? Is there actually any test case where this code produces correct output? Did you make a plan before writing the code? Did you check that the algorithm works with pen and paper? — 463035818_is_not_an_ai, Aug 09 '22 at 11:46
the task description doesnt make sense. If you have an array with n elements and all numbers in the range [1,n] do appear once or twice, then every number must appear exactly once and there are no duplicates — 463035818_is_not_an_ai, Aug 09 '22 at 11:48
@463035818_is_not_a_number yes it works if i remove the vector part, I don't actually know the concept of vectors yet that's why I'm unable to solve this question — Sam's Show, Aug 09 '22 at 11:49
then ask about that in the quesiton. Currently there is no question. You can show the code that works, explain what you changed and explain what you found out while debugging the code — 463035818_is_not_an_ai, Aug 09 '22 at 11:50
@Sam'sShow A vector is not something magical nor advanced. It is a runtime resizable array. https://www.learncpp.com/cpp-tutorial/an-introduction-to-stdvector/. Also you might want to pass it in as a const reference (the input should not be changed by your algorithm) — Pepijn Kramer, Aug 09 '22 at 11:52
@PepijnKramer here changing the input is actually the only way to achieve O(1) *additional* space solution (while keeping O(n) time, of course). — YurkoFlisk, Aug 09 '22 at 20:34
@YurkoFlisk Yes I realize that now to, it is also the reason for those extra limitation on only one or two instances. — Pepijn Kramer, Aug 10 '22 at 04:11
Why do you believe your algorithm works? Explain it like we are a bunch of toddlers. — n. m. could be an AI, Aug 13 '22 at 20:45

score 0 · Answer 1 · answered Aug 13 '22 at 20:24

0

This problem can not be solved in O(n) time and O(1) space. You either need O(n log n) time or O(n) space.

The way the solutions to this gets around this is to hide is to hide the extra space required in the input data. Specifically since the input is ìnt but only numbers between 1 and n the sign bit of the input is free for use by the algorithm.

So go through the input and for every x check if input[abs(x)-1] is positive. If so then set it to negative, otherwise add abs(x) to the output.

This requires O(n) space but it's not extra space.

answered Aug 13 '22 at 20:24

Goswin von Brederlow

11,875
2
24
42

1

Not really. It is possible to do that even if you don't have a sign bit to spare (say your array is uint8_t and the range is such that all the bits are used). The key is the ability to modify the input. It is easy to sort it in O(n) using a non-comparison-based algorithm. – n. m. could be an AI Aug 13 '22 at 21:30
@n.1.8e9-where's-my-sharem. Except you need something like bucket sort, which takes `O(n * log value_size)` and in this case `value_size == n`. You can't sort `n` values in the range `[1-n]` in less than `O(n log n)`, that only works when you have a limited range. – Goswin von Brederlow Aug 14 '22 at 04:28
Oh well you don't quite need to sort. The central part of the algorithm goes like this `for (i = 0; i < size; ++i) { while (input[i] = input[input[i]-1]) { swap(input[i], input[input[i]-1]); } }` This almost sorts the array, not fully but enough for our purposes. I think this is O(n) because each swaps puts one element to its position, and once it's in its position it never moves out, so you don't need more than n swaps. After this all numbers that are not in their places are duplicates. – n. m. could be an AI Aug 14 '22 at 06:38
And of course everything was invented before us https://stackoverflow.com/questions/5739024/finding-duplicates-in-on-time-and-o1-space – n. m. could be an AI Aug 14 '22 at 09:15
@n.1.8e9-where's-my-sharem. Not sure about that `while` condition but the idea of swapping each number `x` so it's placed at index `x-1` is basically the same as using the sign bit. Using the input to hide `O(n)` memory. The way all in-place algorithms use to become "no extra memory". Note: The sign method allows for it being non-destructive if you remove the sign bit again at the end. The swapping is destructive but works without needing that extra bit. – Goswin von Brederlow Aug 14 '22 at 18:58

Find All Duplicates in an Array using XOR method c++

1 Answers1