Post date: Jul 16, 2013 10:44:37 PM
Problem
You are given an array of n integers which can contain integers from 1 to n only .
Some elements can be repeated multiple times and some other elements can be absent from the array .
Write a running code on paper which takes O(1) space apart from the input array and O(n) time to
print which elements are not present in the array and the count of every element
which is there in the array along with the element number .
NOTE: The array isn't necessarily sorted.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Compute the frequency of each element in an array
Created Data : 17-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
void PrintFrequent(int arr[],int len)
{
int pos = 0;
while(pos < len)
{
int expectedPos = arr[pos] - 1;
if(arr[pos] > 0 && arr[expectedPos] > 0){
swap(arr[pos], arr[expectedPos]);
arr[expectedPos] = -1;
}
else if(arr[pos] > 0){
arr[expectedPos] --;
arr[pos ++] = 0;
}
else{
pos ++;
}
}
for(int i = 0; i < len; ++i){
cout << (i + 1) << "----" << abs(arr[i]) << endl;
}
cout << endl;
}
void DoTest(int* arr, int len)
{
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(3) << arr[i];
}
cout << endl;
cout << "The output is " << endl;
PrintFrequent(arr, len);
}
// Assume the len >= max(arr[i])
int main(int argc, char* argv[])
{
int arr[] = {9,9,9,9,9,9,9,8,7,9,9};
DoTest(arr, sizeof(arr)/ sizeof(arr[0]));
int arr1[] = {1};
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]));
int arr3[] = {4, 4, 4, 4};
DoTest(arr3, sizeof(arr3)/ sizeof(arr3[0]));
int arr2[] = {1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1};
DoTest(arr2, sizeof(arr2)/ sizeof(arr2[0]));
int arr4[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
DoTest(arr4, sizeof(arr4)/ sizeof(arr4[0]));
int arr5[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
DoTest(arr5, sizeof(arr5)/ sizeof(arr5[0]));
int arr6[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
DoTest(arr6, sizeof(arr6)/ sizeof(arr6[0]));
return 0;
}
Output
The array is
9 9 9 9 9 9 9 8 7 9 9
The output is
1----0
2----0
3----0
4----0
5----0
6----0
7----1
8----1
9----9
10----0
11----0
The array is
1
The output is
1----1
The array is
4 4 4 4
The output is
1----0
2----0
3----0
4----4
The array is
1 3 5 7 9 1 3 5 7 9 1
The output is
1----3
2----0
3----2
4----0
5----2
6----0
7----2
8----0
9----2
10----0
11----0
The array is
3 3 3 3 3 3 3 3 3 3 3
The output is
1----0
2----0
3----11
4----0
5----0
6----0
7----0
8----0
9----0
10----0
11----0
The array is
1 2 3 4 5 6 7 8 9 10 11
The output is
1----1
2----1
3----1
4----1
5----1
6----1
7----1
8----1
9----1
10----1
11----1
The array is
11 10 9 8 7 6 5 4 3 2 1
The output is
1----1
2----1
3----1
4----1
5----1
6----1
7----1
8----1
9----1
10----1
11----1
Press any key to continue . . .