Even and odd elements at even and odd positions

Even and odd elements at even and odd positions

  January 31, 2018    

---

Approach 1:
Maintain 2 arrays
1 for even and another for odd and print them.
O(n) time and Space

Code:

     public static void evenOddpos(int arr[],int n)
{
List<Integer> even=new ArrayList<Integer>();
List<Integer> odd=new ArrayList<Integer>();
for(int x:arr)
{
if((x&1)==1)
{
odd.add(x);
}
else
even.add(x);
}
int i=0,j=0;
int s=even.size(),s2=odd.size();
while(i<s && j<s2)
{
System.out.print(even.get(i++)+" ");
System.out.print(odd.get(j++)+" ");
}
while(i<s)
System.out.print(even.get(i++)+" "); 
while(j<s2)
System.out.print(odd.get(j++)+" ");
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
evenOddpos(arr,n);
    System.out.println();
}
}



Approach 2:

Maintain 2 pointers and look for even/odd element and print them
O(n) time and O(1) Space

Code:

public static int getelement(int arr[],int pos,boolean flag,int n)
{
if(flag)
{
while(pos<n && (arr[pos]&1)==1)
{
++pos;
}
}
else{
  while(pos<n && (arr[pos]&1)==0)
{
++pos;
}
}
return pos;
}
     public static void evenOddpos(int arr[],int n)
{
int epos=0,opos=0;//even odd position pointer
boolean i=true;
while(epos<n && opos<n)
{
if(i)
{
epos=getelement(arr,epos,true,n);
if(epos<n)
System.out.print(arr[epos++]+" "); 
}
else
{
opos=getelement(arr,opos,false,n);
if(opos<n)
System.out.print(arr[opos++]+" "); 
}
i=!i;
}
// System.out.println("\n odd pos : "+opos+" even pos "+epos);
while(epos<n)
    if((arr[epos++]&1)==0)
{System.out.print(arr[--epos]+" ");
     ++epos;
} 
while(opos<n)
if((arr[opos++]&1)==1)
{System.out.print(arr[--opos]+" ");
     ++opos;
}
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
evenOddpos(arr,n);
    System.out.println();
}
}