I have an array of elements.
Think each of the element as competitors, and a tournament is going to rank them.
The output of the program is showing elements at each level.
Here's the code:
#include <stdio.h>
#include <stdlib.h>
bool isPowerOfTwo (int x)
{
/* First x in the below expression is for the case when x is 0 */
return x && (!(x&(x-1)));
}
// modified
int log_2(unsigned int n) {
int bits = 0;
if (!isPowerOfTwo(n))
bits++;
if (n > 32767) {
n >>= 16;
bits += 16;
}
if (n > 127) {
n >>= 8;
bits += 8;
}
if (n > 7) {
n >>= 4;
bits += 4;
}
if (n > 1) {
n >>= 2;
bits += 2;
}
if (n > 0) {
bits++;
}
return bits;
}
int second_minima(int a[],unsigned int n) {
int log_2n = log_2(n);
int **p = (int **) (malloc(log_2n * sizeof(int *)));
int i, j, k;
for (i = 0, j = n; i < log_2n; i++) {
j = j&1 ? j/2+1 : j/2;
p[i] = (int *)(malloc(j * sizeof(int)));
}
for (i = 0; i < n; i++)
p[0][i] = a[i];
for (i = 1, j = n; i < log_2n; i++) {
for (k = 0; k+1 < j; k += 2) {
if (p[i-1][k] > p[i-1][k+1]) {
p[i][k/2] = p[i-1][k];
//printf("%d\n", p[0][n-1]);
}
else {
p[i][k/2] = p[i-1][k+1];
}
}
if (j&1)
p[i][j/2] = p[i-1][j-1];
j = j&1 ? j/2+1 : j/2;
}
for (i = 0, j = n; i < log_2n; i++) {
for (k = 0; k < j; k++)
printf("%d ",p[i][k]);
printf("\n");
j = j&1 ? j/2+1 : j/2;
}
return 0;
}
main()
{
int n;
scanf("%d", &n);
int a[n];
int i;
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
second_minima(a,n);
return 0;
}
The problem is with this input instance:
Input :
13
12 7 3 18 4 2 16 5 6 17 1 8 9
Output :
12 7 3 18 4 2 16 5 6 17 1 8 12
12 18 4 16 17 8 12
18 16 17 12
18 17
18
Correct Output :
12 7 3 18 4 2 16 5 6 17 1 8 9
12 18 4 16 17 8 9
18 16 17 9
18 17
18
The problem is it is turning the last element of level 0 to first element.
This is occuring at line 49. I dont know why it is changing p[0][n-1] to p[1][0].
Can any one explain the fault.
I have tested it with other inputs, its giving right answer.
