The question is: Given an array of integers nums containing n 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number.

Here is my code:

int findDuplicate(vector<int>& nums) {
int pin = 0;
        for(int i = pin   1; i < nums.size(); i   ){
            if(nums.at(pin) == nums.at(i)){
                return nums.at(pin);
            }
            pin  ;
        }
    return -1;
   }

Sample input in which I am getting an error: [3,1,3,4,2]

Here the output should be 3 but I am getting -1....I have already solved it with other approach but I want to know what error I am making in this approach....

CodePudding user response：

In your code, pin goes from 0 to N-1, i goes from 1 to N. They both iterate in lockstep, which means that you are looking only at pairs of consecutive elements, not all possible pairs. Your method will pass test cases when the two identical numbers are adjacent in the vector.

You can make your approach work by sorting the vector. That's an O(M log N) operation that will guarantee the adjacency of the duplicate elements.

For sufficiently small N, you can use the fact that the sum of the non-duplicate portion of the list will be equal to N * (N 1). Computing the sum of the entire vector is O(N).

For large N, the sum may trigger overflow UB, but most architectures that I've worked with will give you a result modulo 2^32 or whatever the integer size is. You can make the same comparison on the remainder in that case.

CodePudding user response：

yeah you are only checking ( or comparing ) two consecutive values like the first integer is only compared to the second but it has to be compared with all the values , you can simply do it by creating two for loops ( time complexity O(N^2) ) or by some other logic to make the time complexity in O(N) .