# Thread: How to find repeated number in the sequence

1. ## How to find repeated number in the sequence

I have no idea how to write program to find repeated number in the given sequence

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

Program output : Number 1 repeats 2 times

My attempt to make algorithm

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

is 6 == 4 ? if yes then 6 is repeated and if no then look for next element

is 6 == 2? if yes then 6 is repeated and if no then look for next element

is 6 == 1? if yes then 6 is repeated and if no then look for next element

is 6 == 3? if yes then 6 is repeated and if no then look for next element

is 6 == 1? if yes then 6 is repeated and if no then look for next element

is 4 == 2? if yes then 4 is repeated and if no then look for next element

is 4 == 1? if yes then 4 is repeated and if no then look for next element

is 4 == 3? if yes then 4 is repeated and if no then look for next element

is 4 == 1? if yes then 4 is repeated and if no then look for next element

is 2 == 1? if yes then 2 is repeated and if no then look for next element

is 2 == 3? if yes then 2 is repeated and if no then look for next element

is 2 == 1? if yes then 2 is repeated and if no then look for next element

is 1 == 3? if yes then 1 is repeated and if no then look for next element
is 1 == 1? if yes then 1 is repeated and if no then look for next element

is 3 == 1? if yes then 3 is repeated and if no then stop 2. Have you considered sorting the data?

Don't forget functions are your friends.

Your current "algorithm" looks very time consuming, especially as the number of samples increase. 3. Originally Posted by jimblumberg Your current "algorithm" looks very time consuming, especially as the number of samples increase.
just for basic understanding, do you know how that algorithm can be implement in program ?

Note : not asking complete program just asking process or pescudo code 4. 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. 5. 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. 6. Originally Posted by laserlight If by "that algorithm" you're asking for an algorithm that is not so time-consuming, then the answer lies here:

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.
my second option is sorting because I don't know much about it
I have practiced with basics It would to early to jump on sorting method, ofcourse I will learn but not now. so that's why i want to solve it without sorting method. 7. Originally Posted by Salem 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

in simple way if i ask to someone who doesn't have programming knowledge how his brain work to find repeated number, what does he think to find repeated number ? 8. > 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. 9. Originally Posted by Salem > 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.
That's what I am trying to do it ?

so can you give idea , pesudo code be batter 10. 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. 11. 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. 12. 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 ;

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;
}``` 13. I just realised a small mistake in the above code.
The statement if (RunLength != 0) should be (RunLength != 1). Popular pages Recent additions element, number, numbers[, repeated, sequence 