Thread: 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..

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

@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

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

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.

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

thanks ill do that

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

Originally Posted by std10093

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

And the above(OP) is Quadratic.

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.)

Originally Posted by manasij7479

And the above(OP) is Quadratic.

If you mean the code of theju112 this is true.

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