Thread: How to find repeated number in the sequence

If by "that algorithm" you're asking for an algorithm that is not so time-consuming, then the answer lies here:

Originally Posted by jimblumberg

Have you considered sorting the data?

If the input is sorted, then you only need a single pass over the input and no (or rather a small constant amount of) extra space to print all the repeated numbers and their counts.

Jim already told you - sort the data.

Numbers[ ] = [ 6, 4, 2, 1, 3, 1 ]
becomes
Numbers[ ] = [ 1, 1, 2, 3, 4, 6 ]

Then all the like numbers will be together, and all you have to do is count the run length of each number.

> so can you give me idea How it can be achieve without sorting
Then you have no better option than repeated searching for each element.

You've written down already what you need to do.

It's the same kind of nested loop you might use for say bubble sort.

Well, there are faster methods than repeated searching that don't involve sorting the input array, but usually people learn to sort before they learn balanced binary trees and hash tables.

If you know that the input numbers will be in a very small range as in your example, you can use a lookup table to map the numbers to their counts.

This is the simplest way of finding repeated elements i.e. sorting the array. Here, I use a slower sorting algorithm (Selection Sort) that you might've learnt already. You can improve that. There are other ways, both horrible and better, like mentioned by the others, but there's no point getting into the details as you had to ask for pseudo-code for a simple problem. If you want to answer without sorting and also have your life made easier, switch to C++, and use STL containers like maps and sets.

Code:

void swap (int& L, int& R) {
	int temp = L;
	L = R;
	R = temp;
}


void sort (int* Array, int Size) {
    for (int i = 0; i < Size - 1; ++i) {
        int idx = i;
        for (int j = i + 1; j < Size; ++j)
			if (Array [j] < Array [idx])
				idx = j;
        swap (Array [idx], Array [i]);
    }
}


void printArray (int* Array, int Size) {
	for (int i = 0; i < Size; ++i)
		printf("%d ", Array [i]);
}


int main() {
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr); cout.tie(nullptr);
//	cout.precision(10);
//	cout << fixed;// << boolalpha;


	// Sufficiently large array
	int Numbers [1000];


	int NumberOfElements;
	scanf("%d", &NumberOfElements);
	assert(NumberOfElements <= 1000);


	for (int i = 0; i < NumberOfElements; ++i)
		scanf("%d", Numbers + i);


	printf("\nThe Array you entered: ");
	printArray(Numbers, NumberOfElements);


	// The algorithm jimblumberg is talking about that sorts elements
	sort(Numbers, NumberOfElements);


	printf("\n\nThe sorted Array: ");
	printArray(Numbers, NumberOfElements);


	printf("\n\nStatistics:\n\n");
	// The algorithm that even my 10 year old cousin can come up with and code without pseudo-code
	for (int i = 0, j = 0; i < NumberOfElements; ++i) {
		int CurrentElementBeingCheckedIfRepeated = Numbers [i];
		// The variable Salem is talking about that counts number of duplicates
		int RunLength = 1;
		for (j = i + 1; j < NumberOfElements; ++j) {
			if (Numbers [j] == CurrentElementBeingCheckedIfRepeated)
				++RunLength;
			else break;
		}
		i = j - 1;
		if (RunLength != 0)
			printf("Element %d has %d duplicates\n", CurrentElementBeingCheckedIfRepeated, RunLength);
	}


	return 0;
}

I just realised a small mistake in the above code.
The statement if (RunLength != 0) should be (RunLength != 1).