Sponsored
Sponsored
This approach uses a hashmap (or dictionary) to store the count of each element in the array. By iterating through the array and updating the map, we can easily identify the element that repeats n times by checking the count value.
Time Complexity: O(N), where N is the length of the nums array because we iterate over it once.
Space Complexity: O(1), since the hashmap is of a fixed size of 10001.
1#include <stdio.h>
2#include <stdlib.h>
3
4int repeatedNTimes(int *nums, int numsSize) {
5 int *hash = (int *)calloc(10001, sizeof(int));
6 for (int i = 0; i < numsSize; i++) {
7 hash[nums[i]]++;
8 if (hash[nums[i]] > 1) {
9 free(hash);
10 return nums[i];
11 }
12 }
13 free(hash);
14 return -1; // This will never be reached according to the problem constraints
15}
16
17int main() {
18 int nums[] = {1, 2, 3, 3};
19 int result = repeatedNTimes(nums, 4);
20 printf("%d\n", result);
21}
22The C solution uses an array hash of fixed size to act as a hashmap to count occurrences of each number. As soon as a number appears more than once, the function returns that number and frees the allocated memory.
In this method, we first sort the array. If an element is repeated n times and the rest are unique, the repeated element must be at the center of the sorted array, appearing consecutively. Checking the middle indexes should reveal the repeated element.
Time Complexity: O(N log N), due to the sorting process.
Space Complexity: O(1) in place sorting.
1#
The C solution sorts the array with qsort, then checks adjacent elements for equality. The repeated element will be found in this check.