Find duplicate number in array

Question

I am debugging a problem below and posting a solution from which I am debugging and working, a solution or the like is posted in several forums, but I think the solution has an error when num [0] = 0 or even num [x] = x? I'm right? Please feel free to correct me if I am wrong.

Given the nums array containing n + 1 integers, where each integer is between 1 and n (inclusive), prove that there must be at least one duplicate number. Assuming there is only one duplicate number, find the duplicate.

Note: You must not modify the array (suppose the array is read-only). You should use only constant, O (1) extra space. Your runtime complexity should be less than O (n2). There is only one duplicate number in the array, but it could be repeated more than once.

int findDuplicate3(vector<int>& nums) { if (nums.size() > 1) { int slow = nums[0]; int fast = nums[nums[0]]; while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } fast = 0; while (fast != slow) { fast = nums[fast]; slow = nums[slow]; } return slow; } return -1; } 

Answer 1

• Start with two pointers to the first element: fast and slow.
• Define “movement” as rapidly increasing by 2 steps (positions) and slowly by 1.
• After each step, check if the same node is pointed slowly and quickly.
• If there is a cycle, at some point they will be. This is because after they are in the cycle, the speed moves twice as fast as the slow one, and ultimately "collides" with it.
• Say they meet after k steps. This is NOT a MANDATORY item repeated, as it may not be the first item in a loop received from outside the loop.
  Call this element X.
• Note that fast step is 2k times, and slow step is k.
• Quick switch to zero.
• Drive fast and slow repeatedly with ONE STEP EACH, comparing after each step.
• Please note that after the other k steps, the slow one will be moved a total of 2 thousand steps and will accelerate a total of k steps from the very beginning, so they will both point to X again.
• Note that if the previous step is in a loop for both of them, they both pointed to X-1. If the previous step was only on the loop for slow, then they pointed to different elements.
• Same for X-2, X-3, ...
• So, the first time they point to the same element, this is the first element of the loop, obtained from outside the loop, which is the repeating element that you are looking for.

Answer 2

Below is my code that uses the Floyd search algorithm:

 #include <iostream> #include <vector> using namespace std; int findDup(vector<int>&arr){ int len = arr.size(); if(len>1){ int slow = arr[0]; int fast = arr[arr[0]]; while(slow!=fast){ slow = arr[slow]; fast = arr[arr[fast]]; } fast = 0; while(slow!=fast){ slow = arr[slow]; fast = arr[fast]; } return slow; } return -1; } int main() { vector<int>v = {1,2,2,3,4}; cout<<findDup(v)<<endl; return 0; } 

Comment This works because zeros are not allowed, so the first element of the array is not part of the loop, so the first element of the first loop that we find applies to both outside and inside the loop. If zeros were allowed, this would not work if arr [0] were in the loop. For example, [0,1,1].

Answer 3

The sum of integers from 1 to N = (N * (N + 1)) / 2 . You can use this to find a duplicate - sum integers in an array, and then subtract the above formula from the sum. This is a duplicate.

Update . The above solution is based on the (possibly invalid) assumption that the input array consists of values ​​from 1 to N plus one duplicate.

Answer 4

Since you cannot use any extra space, exclude the use of another hash table.

Now, approaching the hashing of an existing array, it can be achieved if we are allowed to modify the array in place.

Algo:

1) Start with the first element.

2) Hash the first element and apply the conversion to the hash value. Let's say this conversion makes the value -ve.

3) Go to the next item. Hold the item and verify that the transform has been applied before applying the transform.

4) If yes, then the item is a duplicate.

the code:

  for(i = 0; i < size; i++) { if(arr[abs(arr[i])] > 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else cout<< abs(arr[i]) <<endl; } 

This conversion is necessary, because if we want to use a hash approach, then there must be a collision to hash the same key.

I don’t think about how hashing can be used without any extra space and not changing the array.