There is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory.
Strategy:
To solve this problem, we must keep track of elements in order to figure out which one is duplicate. However, regardless of method, we must not use any extra memory. Here is where we must depend on the information given by the problem.
We know that each element's value is between 1 and N, so if we increase that value by (N + 1), the modulus of that value and N + 1 is still the same. For example, modulus of 2 and (N + 1) is 2 and modulus of 2 + N + 1 is still 2. Thus, we can mark a visited element by adding N + 1 into its value or any element's value in the array because that doesn't change its modulus with N + 1 at all!
Furthermore, we know that each element's value is between 1 and N. Hence, we can use each element's value as a key and the element at array[key] as the mark. For example, if the current element is 4 then we can check if its value has been visited, and thus a duplicate, by looking at the value of the element at index 4 in the array, if the current element is 2 the we check the value of the element at index 2 in the array, and so on.
One final point, we need to traverse the array and check each element, so we need a loop that run till we find the duplicate or till we reach the end of the array. The problem with such loop is that it needs additional counter / sentinel value as the loop's termination condition! That requires memory allocation. Fortunately, we know that the first element is not a duplicate because there is no other element in front of it. Thus, we can use the first element in the array as our counter.
Example:
Lets take the given array as 1 3 2 1 1 3
Alternative Method:
Keep one pointer at first index and swap the value at first index with the value at index=value at first position.That means 1 will be swapped with 1 only.If a[i]==i then move the pointer forward.Then at index 2 we get the value as 3.So swap 3 with 2.Now again a[2]=2 So move the pointer forward.In this manner if an elemnt i is already there at a[i] then that is first duplicate.
Strategy:
To solve this problem, we must keep track of elements in order to figure out which one is duplicate. However, regardless of method, we must not use any extra memory. Here is where we must depend on the information given by the problem.
We know that each element's value is between 1 and N, so if we increase that value by (N + 1), the modulus of that value and N + 1 is still the same. For example, modulus of 2 and (N + 1) is 2 and modulus of 2 + N + 1 is still 2. Thus, we can mark a visited element by adding N + 1 into its value or any element's value in the array because that doesn't change its modulus with N + 1 at all!
Furthermore, we know that each element's value is between 1 and N. Hence, we can use each element's value as a key and the element at array[key] as the mark. For example, if the current element is 4 then we can check if its value has been visited, and thus a duplicate, by looking at the value of the element at index 4 in the array, if the current element is 2 the we check the value of the element at index 2 in the array, and so on.
One final point, we need to traverse the array and check each element, so we need a loop that run till we find the duplicate or till we reach the end of the array. The problem with such loop is that it needs additional counter / sentinel value as the loop's termination condition! That requires memory allocation. Fortunately, we know that the first element is not a duplicate because there is no other element in front of it. Thus, we can use the first element in the array as our counter.
Example:
Lets take the given array as 1 3 2 1 1 3
Alternative Method:
Keep one pointer at first index and swap the value at first index with the value at index=value at first position.That means 1 will be swapped with 1 only.If a[i]==i then move the pointer forward.Then at index 2 we get the value as 3.So swap 3 with 2.Now again a[2]=2 So move the pointer forward.In this manner if an elemnt i is already there at a[i] then that is first duplicate.
No comments:
Post a Comment