How to find repeated number in a array, need algorithm! Urgent!

allenfanwenyuan · #1 21-May-2007, 02:56

How find a repeated number in a array .....who can tell me the algorithm!
like
1 2 3 5 6 1
output
1

dlp · #2 21-May-2007, 10:35

Pseudocode:

Code:

numbertosearchfor = somenumber;
countofnumber = 0;

for each element in array:
    if element in array == numbertosearchfor:
        increment countofnumber;

if countofnumber is greater than 1:
    say so

Take your number. Compare it to every element in the array. If it exists in the array, count it. If at the end of the array, your count is greater than 1, say that the number you found exists in the array more than once.

Take that idea, make some C++ code, and post any questions

Peter_APIIT · #3 22-May-2007, 02:34

Actually, this is quite easy.

Assume the first number array is repeated number and compare to the element of array. If they equal, return number, else return 0;

I hope this may help you understand C++ better.

dlp · #4 22-May-2007, 04:22

Quote:

Originally Posted by Peter_APIIT

Assume the first number array is repeated number and compare to the element of array. If they equal, return number, else return 0;

1. Why assume it is already repeating before searching through array? That would mean the first match which could be the only match and therefore not repeating, would return true.

2. Why return 0? What if the value you're looking for as a repeat value is 0?

Peter_APIIT · #5 22-May-2007, 07:36

Quote:

1. Why assume it is already repeating before searching through array? That would mean the first match which could be the only match and therefore not repeating, would return true.

The logic behind this scene is if i not assume the first array to be repeated number, then you need to compare many times but if you assume the first array is repeated number, then you only need to compare the array size - 1;

Quote:

2. Why return 0? What if the value you're looking for as a repeat value is 0?

This is just an example. What i doing here is if i find the repeated number, then i return true(1), else false(0), you can return the repeated number.

I hope this may helps.

dlp · #6 22-May-2007, 10:10

Quote:

Originally Posted by Peter_APIIT

The logic behind this scene is if i not assume the first array to be repeated number, then you need to compare many times but if you assume the first array is repeated number, then you only need to compare the array size - 1;

True. That's the fun part of the method. You can wrap the pseudocode you use as a base and make "somenumber" anything, including an element of the array. If you want, you can use a for loop around it to check every number in the array.

Quote:

Originally Posted by Peter_APIIT

This is just an example. What i doing here is if i find the repeated number, then i return true(1), else false(0), you can return the repeated number.

I hope this may helps.

True, and this would be more efficient with larger arrays.

Peter_APIIT · #7 22-May-2007, 20:51

I hope this can help other programmers.

ahbi82 · #8 25-May-2007, 17:42

Quote:

Originally Posted by dlp

Pseudocode:

Code:

numbertosearchfor = somenumber;
countofnumber = 0;
 
for each element in array:
    if element in array == numbertosearchfor:
        increment countofnumber;
 
if countofnumber is greater than 1:
    say so

Take your number. Compare it to every element in the array. If it exists in the array, count it. If at the end of the array, your count is greater than 1, say that the number you found exists in the array more than once.

Take that idea, make some C++ code, and post any questions

Just trying to have a clearer picture..... I think the question is to find if the array has a repeated number in it, and not find a particular number in it. Correct me if i am wrong.....

I have two methods in mind.

Method 1 (easiest)
----------------------
Using nested for loops

Code:

int findRepeat( int* a , int arraySize)
{
    int i, j;
 
    for( i = 0; i < arraySize; i++)
    {
         for( j = i+1; j < arraySize; j++)
         {
              if( a[i] == a[j] )
                  return 1;
         }
    }
 
    return 0;
}
 
int main(int argc, char *argv[])
{
    int array[5] = { 1, 2, 2, 4, 5 };
 
    if( findRepeat(array, 5) )
        printf("Found repeated number in array!\n");
    else
        printf("No repeat number in array!\n");
 
      return 0;
}

Method 2
----------------------
First sort the array using some sorting algorithm probably quick sort. Maybe u can find in <algorithm> if i am not wrong. Then traverse the sorted array. Comparing the current element with the next element. If equal return some value indicationg repeated found.

The difference is that method one uses nested loop while method 2 usesjust one for loop. As the array size grows method 2 will be a better choice if a suitable sorting algorithm is used.

To return the repeated number just return the value...... BUT this only work forj ust ONE repeated number. If u want to find the repeated NUMBERS, maybe u can use another array/pointer to store the list of repeated number.

Hope this helps!!!!

allenfanwenyuan · #9 28-May-2007, 02:17

Thank you guys for helping me , I actually done this part by myself ,there is code ,

CPP / C++ / C Code:

bool valid2(const int list1[])
{
     int tmp;
     for(int i=0;i<MAXSIZE;i++)
     {
             tmp=list1[i];
             for(int j=0;j<MAXSIZE;j++)
             {
                if(list1[j]==tmp && (j>i))
                  {
                  return false;
                  }
             }
     }
     return true;
}

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Converting a number amount to text	Godzilla	C++ Forum	5	31-Mar-2006 11:38
Need help deleting the last element in the array	headphone69	C++ Forum	2	15-Mar-2006 19:31
template comiling problems - need expert debugger!	crq	C++ Forum	1	01-Feb-2005 21:26
Using an array and finding the element number (subscript)	tommy69	C Programming Language	27	05-Apr-2004 12:23

How to find repeated number in a array, need algorithm! Urgent!

Re: How to find repeated number in a array, need algorithm! Urgent!

Re: How to find repeated number in a array, need algorithm! Urgent!

Re: How to find repeated number in a array, need algorithm! Urgent!

Re: How to find repeated number in a array, need algorithm! Urgent!

Re: How to find repeated number in a array, need algorithm! Urgent!

Re: How to find repeated number in a array, need algorithm! Urgent!

Re: How to find repeated number in a array, need algorithm! Urgent!

I done it in my way .