Vimil
BAN USERHere is one solution.
public static int memberOfGroup(int x, int n)
{
int x1 = x;
int groupId = x;
do
{
x = n + (x-1);
while(x%2==0)
{
x = x/2;
}
if(groupId>x)
{
groupId = x;
}
}while(x!=x1);
return groupId;
}
public static int[] reorderArray(int[] a)
{
int n = a.length;
int count = 0;
int i = 1;
while(true)
{
int cur = i;
int next = i;
int temp = a[cur];
do
{
next = (2*cur)/n + (2*cur)%n;
int temp1 = a[next];
a[next] = temp;
temp = temp1;
count++;
cur = next;
}
while(next!=i);
if(count<n-2)
{
do
{
i+=2;
if(memberOfGroup(i, n)==i) break;
}while(true);
}
else
{
break;
}
}
return a;
}
public static int[] createArray(int n)
{
if(n%2==0)
{
int[] a= new int[n];
for(int i=0; i< n/2; i++)
{
a[i] = i;
}
for(int i=n/2; i< n; i++)
{
a[i] = i-(n/2);
}
return a;
}
return null;
}
public static void main(String[] args)
{
int[] a = createArray(128);
a = reorderArray(a);
for(int i=0; i<a.length; i++)
{
System.out.println(a[i]);
}
}
I am not sure how to compute the time complexity of this algorithm though
- Vimil November 10, 2007
According to the question there are lines that may not fit into main memory. It would be better to have the hashmap store the checksum of each line as the key and the line number as the value.
- Vimil November 10, 2007