single traverse in array problem......

[sumitshining]

if there r around 100000 elements in an array then how to count no of elements with exactly two repetitions in a single traverse????

[weaknessforcats]

You can't count the number of elements in an array becuse there is no marker to tell you wne youhave reached the array bound.

Maybe you could explain further what it is you have to do.

[sumitshining]

You can't count the number of elements in an array becuse there is no marker to tell you wne youhave reached the array bound.

Maybe you could explain further what it is you have to do.

if the no of elements in an array is say 1000000........ .then if you have to count those elements which are repeated exactly twice.......... in a single traverse....... how would u do that????????tha ts d exact ques.......

[JosAH]

if the no of elements in an array is say 1000000........ .then if you have to count those elements which are repeated exactly twice.......... in a single traverse....... how would u do that????????tha ts d exact ques.......

Repeated twice in a row (next to each other) or repeated twice anywhere in the array?

kind regards,

Jos

[weaknessforcats]

By repeated twice, do you mean 3 occurrances of that value? That is, the original plus two repetitions.

However it goes, build a symbol table. In this case binary tree should do it. Have the node contain the value plus the count. Populate the tree with the array values by accessing the tree first and if the value is there, just increment the count. Otherwise, add the vaoue with a count of 1.

Then just read the tree for all values with a count of 3.

[ashitpro]

ignore thissssssssssss sssssssssssssss ssssssss

[ashitpro]

declare two temporary arrays of size maximum integer value..(say 32767)
We will use first matrix for positive numbers in your array..
and second for negative values in array...

int counter=0;
int positive[32767]={0}; //initialize all to zero
int negative[32767]={0};
for(i=0;i<1000000;i++)
{
    if(YourArray[i]<0)  //for negative numbers
    {
            if(negative[YourArray[i] * -1]==1)
            {
                 counter++;  //increase counter cause we got second occurrence
                 negative[YourArray[i] * -1]++; 
            }
            else if(negative[YourArray[i] * -1]==2)
            {
                  counter--; //we got third occurence..so minus the counter by one
            }
            else //we come accross this number first time..
            {
                negative[YourArray[i] * -1]++;
            }

    }
   else  //for positive numbers
   {
           if(positive[ YourArray[i] ]==1)
            {
                 counter++;  //increase counter cause we got second occurrence
                 positive[ YourArray[i] ]++; 
            }
            else if(positive[ YourArray[i] ]==2)
            {
                  counter--; //we got third occurence..so minus the counter by one
            }
            else //we come accross this number first time..
            {
                positive[ YourArray[i] ]++;
            }


   }

}

counter will represent the final count...

[sumitshining]

Repeated twice in a row (next to each other) or repeated twice anywhere in the array?

kind regards,

Jos

sorry.......... ..actually it is repeated only once........... ..that is only two occurence...... ......