Re: [algogeeks] unsorted array problem

[tech coder]

it can be done in O(N) by using XOR ing the elements
1: Xor all the elemnts since those elemnts that even freq will nullify each
other we get number taht will tell in which the two required number differ.
2: divide  the array in two sets  on the basis of bit in which numbers
differ
3:1 element will  be in one set another will be in another set
4: XOR both the sets again we get both the elemts
On Thu, Aug 25, 2011 at 12:50 PM, Umesh Jayas algowithum...@gmail.comwrote:



 int main()
 {
 int arr[]={1,2,5,1,5,1,1,3,2,2,};
 int elements = sizeof(arr)/sizeof(arr[0]);
 int count=1;
 int num;
 sort(arr,arr+elements);

 num=arr[0];
 for(int i=1;ielements;i++)
 {
 if(arr[i]==num)
 count++;
 else
 {
 if(count%2==0)
 { num=arr[i];
  count=1;}
 else
  {cout\narr[i-1];
  count=1;
  num=arr[i];
  }
 }
 }
 getch();
 }

 complexity: O(nlogn)

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] unsorted array problem

[Rahul Verma]

@Umesh I really appreciate your solution and thinking to understand the 
complexity of the program.

Actually I don't have that much idea about the *how to calculate complexity 
of any program*. So could you please show some light on the evaluation 
procedure of complexity.

Rahul Verma

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/Lw-yo4fG0kgJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] unsorted array problem

[Umesh Jayas]

int main()
{
int arr[]={1,2,5,1,5,1,1,3,2,2,};
int elements = sizeof(arr)/sizeof(arr[0]);
int count=1;
int num;
sort(arr,arr+elements);

num=arr[0];
for(int i=1;ielements;i++)
{
if(arr[i]==num)
count++;
else
{
if(count%2==0)
{ num=arr[i];
 count=1;}
else
 {cout\narr[i-1];
 count=1;
 num=arr[i];
 }
}
}
getch();
}

complexity: O(nlogn)

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.