Like Tree1Likes
  • 1 Post By ZuK

is there a logic error in this code?

This is a discussion on is there a logic error in this code? within the C++ Programming forums, part of the General Programming Boards category; hey guys i have written this function to list the elements in an array without repetition. i.e if an int ...

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    91

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

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    > for(j=0;j<size;j++)
    How many valid records do you have?
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    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

  4. #4
    Registered User
    Join Date
    Aug 2011
    Posts
    91
    Quote Originally Posted by ZuK View Post
    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
    Last edited by theju112; 08-29-2012 at 07:41 AM.

  5. #5
    Registered User
    Join Date
    Aug 2011
    Posts
    91
    @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

  6. #6
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by theju112 View Post
    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
    theju112 likes this.

  7. #7
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 ).
    Last edited by manasij7479; 08-29-2012 at 07:53 AM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  8. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    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.

  9. #9
    Registered User
    Join Date
    Aug 2011
    Posts
    91
    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

  10. #10
    Registered User
    Join Date
    Aug 2011
    Posts
    91
    Quote Originally Posted by std10093 View Post
    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

  11. #11
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    Quote Originally Posted by manasij7479 View Post
    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.
    Last edited by std10093; 08-29-2012 at 07:59 AM.

  12. #12
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by std10093 View Post
    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.)
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  13. #13
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    Quote Originally Posted by manasij7479 View Post
    And the above(OP) is Quadratic.
    If you mean the code of theju112 this is true.

    Quote Originally Posted by manasij7479 View Post
    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

  14. #14
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,420
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Different Logic to optimize this code further.
    By jagu in forum C Programming
    Replies: 2
    Last Post: 10-09-2011, 12:45 PM
  2. Error in logic
    By mesmer in forum C Programming
    Replies: 2
    Last Post: 10-21-2008, 06:42 AM
  3. I can't quite get the logic behind this code...
    By prominababy in forum C Programming
    Replies: 6
    Last Post: 09-26-2008, 02:27 PM
  4. Code logic error
    By 182 in forum C++ Programming
    Replies: 5
    Last Post: 02-21-2006, 04:35 PM
  5. turning my logic into code
    By mustang in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2003, 10:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21