Thread: How to find repeated number in the sequence

  1. #1
    Registered User
    Join Date
    May 2017
    Posts
    127

    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. #2
    Registered User
    Join Date
    May 2010
    Posts
    4,539
    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. #3
    Registered User
    Join Date
    May 2017
    Posts
    127
    Quote Originally Posted by jimblumberg View Post

    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. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,778
    If by "that algorithm" you're asking for an algorithm that is not so time-consuming, then the answer lies here:
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,060
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    May 2017
    Posts
    127
    Quote Originally Posted by laserlight View Post
    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. #7
    Registered User
    Join Date
    May 2017
    Posts
    127
    Quote Originally Posted by Salem View Post
    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. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,060
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    May 2017
    Posts
    127
    Quote Originally Posted by Salem View Post
    > 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. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,060
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,778
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    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;
    }
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  13. #13
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    302
    I just realised a small mistake in the above code.
    The statement if (RunLength != 0) should be (RunLength != 1).
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Program to find repeated number in array
    By vajra11 in forum C Programming
    Replies: 9
    Last Post: 08-31-2018, 09:17 AM
  2. Replies: 8
    Last Post: 12-21-2012, 11:48 PM
  3. Find no of times a no is repeated in a array.
    By Anitrex in forum C Programming
    Replies: 4
    Last Post: 03-18-2012, 06:07 AM
  4. Number repeated thrice
    By anirban in forum Tech Board
    Replies: 19
    Last Post: 03-26-2010, 09:34 AM
  5. To check if a sequence is repeated in a string
    By chatterjee in forum C Programming
    Replies: 6
    Last Post: 08-18-2006, 09:40 PM

Tags for this Thread