# Finding a duplicate number in an array in C

Below is easy level problem it seems:

Given an integer array `nums`, return `true` if any value appears at least twice in the array, and return `false` if every element is distinct.

In Python, if we are writing using hash list or dictionary , its simple. Time complexity will be O(n) and space complexity will be O(n). But one thing I dont understand how the dictionary search happens in Python internally. Does it not use a loop . Please provide your comments.

But if we have to write in C language, simple way is to write in 2 for loops where the time complexity is O(n*n) and space complexity is O(1).

But if we want to write with time complexity of O(n) similar to Python, hash table not possible in my perspective. Why not possible : integer in array can be of any integer value, integer can be 2**31 also. If we need to do hashmap of that integer then hash table should be such big to hold that index value. Can we implement this in C using hash table. Please provide your comments with O(n) time complexity.

Finally I could use merge sort knowledge to implement this. Below is my code: I added prints in comments. these prints may be helpful to understand the functionality.

bool Check4Dup(int* nums, int start, int end);
bool containsDuplicate(int* nums, int numsSize){
int start =0, end= numsSize-1;

return Check4Dup(nums, start, end);
}
bool MergeNcheck(int* nums, int start, int mid, int end)
{
int ii = start, jj=mid+1;
int temp[end-start+1],ind=0;
// printf(“%d line, start %d, mid %d, end %d, num[%d] %d, num[%d] %d , num[%d] %d\n”,
// __LINE__,ii, mid, end, start, nums[start], mid, nums[mid], end, nums[end]);
while (ii<=mid && jj<=end)
{
// printf(“%d line nums[%d] %d, nums[%d] %d\n”,
// __LINE__, ii,nums[ii],jj, nums[jj]);
if (nums[ii] == nums[jj])
return 1;
if (nums[ii]< nums[jj])
temp[ind++] = nums[ii++];
else
temp[ind++] = nums[jj++];
}

while (ii<=mid)
{
temp[ind++] = nums[ii++];
}
while (jj<=end)
{
temp[ind++] = nums[jj++];
}

for (ii=start;ii<=end;ii++)
{
nums[ii]=temp[ii-start];
//printf(“%d line, start %d, end %d, nums[%d] %d\n”,
// __LINE__,start, end, ii, nums[ii]);
}
return 0;
}
bool Check4Dup(int* nums, int start, int end)
{
int mid = (start+end)/2;
bool res = 0;
// printf(“%d line, start %d, end %d\n”, __LINE__,start, end);
if (start < end)
{
//printf(“%d line, start %d, end %d, mid %d, “)
if ((mid != start) && (nums[mid] == nums[start]))
return 1;
if ((mid != end) && (nums[mid] == nums[end]))
return 1;
res = Check4Dup(nums, start, mid);
if (!res)
res = Check4Dup(nums, mid+1, end);
// printf(“%d line, start %d, end %d, mid %d\n”, __LINE__,start, end, mid);
if (!res)
res = MergeNcheck(nums,start, mid, end);
}
return res;
}

--

--