1.

Given an n-element array with elements ranging from 0 to n-1, any of these integers can occur whatever number of times. Using just constant memory space, find those repeating numbers in O(n).

Answer»

The array's numbers vary from zero to n-1, and also the input array is n bytes long. As a result, the input array could be transformed into a HashMap. If an element 'a' is discovered while navigating the array, raise the value of a%nth element by n. By DIVIDING the a%nth element by n, you can get the frequency.

// C++void findDupEle (int NUM[], int n){ for (int i = 0; i < n; i++) { num[num[i] % n] = num[num[i] % n] + n; } cout << "The duplicate elements are : " << endl; for (int i = 0; i < n; i++) { if (num[i] >= n * 2) { cout << i << " " << endl; } } RETURN;}
  • Time Complexity: O(n) as only two traversals are required.
  • Space Complexity: O(1) because no more space is required. Thus, the space complexity remains constant.


Discussion

No Comment Found

Related InterviewSolutions