is there a logic error in this code?

hey guys i have written this function to list the elements in an array without
repetition. i.e if an int array with repeating elements is passed to the function,it should return all the numbers in the array without repeating.

eg:

Code:

---

input={1, 1, -1, 1, 2, 3, 23, 23, 1, 10, 99, -1}

output={1, -1, 2, 3, 23, 10, 99}

---

Code:

---

#include<iostream.h>
#include<stdio.h>


void count(int input1[],int);
int main()
{
        int size;
       
        cout<<endl<<"ENTER SIZE OF ARRAY";
        cin>>size;
        int input[size];
       
        cout<<endl<<"ENTER ELEMENTS OF AN ARRAY TO LIST THE NUMBERS IN IT WITHOUT REPITITION"<<endl;
       
        for(int i=0;i<size;i++)
        cin>>input[i];
       
       
        count(input,size);       
       
}



void count(int input[],int size)
{
        int record[size],j; //note:record array keeps a record of the elements encounterd
        for(int i=0;i<size;i++)
        record[i]=0;
       
        int match=0;
       
        int i,d,index=0;
       
        for(i=0;i<size;i++) //take the elements in input array one by one for comparing with record array
        {
                //cout<<endl<<"input["<<i<<"]="<<input[i];
                match=0; //set flag variable in case the number is already recorded in the record array
               
                for(j=0;j<size;j++)
                {
                        //cout<<endl<<"record["<<j<<"]="<<record[j];
                        if(input[i]==record[j])
                        {
                        //cout<<endl<<record[j];
                        match=1; //if match set flag vaiable
                        }
                }       
               
                if(match==0) // if no record of the element has been made yet copy it into the record
                record[index++]=input[i];       
                //cout<<endl<<"j="<<j;
        }
               
       
       
        for(i=0;i<index;i++)
        cout<<endl<<record[i];

}

---

the above program was not outputting the correct list of elements until these lines were added to the function count:

Code:

---

for(int i=0;i<size;i++)
        record[i]=0;

---

to be honest i dont know what i have done here..i added these lines because i felt that the record array might contain some of the elements in the 'input' array along with the garbage it is initialized with.

i have tested the code a fair number of times after the modification and its giving the correct output.

Could somebody tell me if the reason for the earlier error is what i guessed it to be?

or can you spot any flaw in the logic?


i just need to be sure as the function is gonna be integrated with other..


also I would be happy if somebody could suggest a more efficient logic to solve the thing..

> for(j=0;j<size;j++)
How many valid records do you have?

There is one problem.
If an input is 0 then it will not be in the output.
But you could easily overcome that by changing the inner loop to

Code:

---

for(j=0;j<index;j++)

---

This way you don't even have to initialize the output array to 0.
Kurt

Quote:

---

Originally Posted by ZuK

There is one problem.
If an input is 0 then it will not be in the output.

---

Sorry forgot specifying that the elements in the input array can only be negative or positive integers..
Apart from this anything else needs repair?

also any logic for a better implementation(faster exec) is welcome

@salemI am not sure if i get your point..elements are added to the record array if they are encountered for the first time...initially the record array contains 0s only.
the size of the record array is set to 'size' variable in case all elements are diferent

Quote:

---

Originally Posted by theju112

Sorry forgot specifying that the elements in the input array can only be negative or positive integers..

---

If you really want to skip 0's then you should check that in the input loop. Counting up to size is not efficient if there are only index valid records.

Kurt

You can improve it by sorting the original list first.
Then, the duplicates will always be adjacent to each other, so the linear search as an inner loop won't be necessary.

Another way, only good if the elements have a small range span, is to make a 'bit set' and set the nth bit to 1 whenever you see an n.
The output is simply the numbers of the positions(adding the range's offset ) in the bit set which are set to 1.

These approaches has a problem that the output elements won't be in the same order as in the input (which is generally not a requirement, anyway ).

A little modification i would do is at loop in line 40.If a match is found then why traversing through the whole array?use keyword break in order to escape the loop.

Code:

---

cout<<endl<<"ENTER SIZE OF ARRAY";
    cin>>size;
    int input[size];
   
    cout<<endl<<"ENTER ELEMENTS OF AN ARRAY TO LIST THE NUMBERS IN IT WITHOUT REPITITION"<<endl;
   
    for(int i=0;i<size;i++)
    cin>>input[i];

---

you mean check for zeroes in the above code right?

actually the count function is gonna be called from somewhere else..thats a really long piece of code..cant paste here.

i have written the main function just for the sake of testing.

Quote:

---

Counting up to size is not efficient if there are only index valid records.

---

thanks ill do that

Quote:

---

Originally Posted by std10093

A little modification i would do is at loop in line 40.If a match is found then why traversing through the whole array?use keyword break in order to escape the loop.

---

thanks

Quote:

---

Originally Posted by manasij7479

You can improve it by sorting the original list first.
Then, the duplicates will always be adjacent to each other, so the linear search as an inner loop won't be necessary.

---

Sort at the best gives you an O(nlogn) complexity.Then the linear search is not necessary,but you still have to go through the array and check how many numbers are duplicate so,actually i do not know if you are improving it or not.Also this method has the drawback of the output you mentioned

EDIT->Also theju112 i would suggest you to check if the variable size that you get from the user is a positive number.

Quote:

---

Originally Posted by std10093

Sort at the best gives you an O(nlogn) complexity.

---

And the above(OP) is Quadratic.

Quote:

---

Then the linear search is not necessary,but you still have to go through the array and check how many numbers are duplicate so,actually i do not know if you are improving it or not.

---

Considering that in linear search the 'results' can be scattered all over the array and in this, the next few elements(i.e..once you get a 'miss' you know that the search is over), I think it is a huge improvement.
(Iterating over the next few elements is practically constant time and after you do so, you don't even have to consider them separately.)

Quote:

---

Originally Posted by manasij7479

And the above(OP) is Quadratic.

---

If you mean the code of theju112 this is true.

Quote:

---

Originally Posted by manasij7479

Considering that in linear search the 'results' can be scattered all over the array and in this, the next few elements(i.e..once you get a 'miss' you know that the search is over), I think it is a huge improvement.
(Iterating over the next few elements is practically constant time and after you do so, you don't even have to consider them separately.)

---

That's very interesting.Thank you for your input.Ok so, if theju112 does not have a problem with array i think that he could do what you said :)

int size;

cout<<endl<<"ENTER SIZE OF ARRAY";
cin>>size;
int input[size];

This is not valid standard C++ code. I'd suggest you learn how to use vectors, as they expand automatically as you push new elements into them.