cplusplus
BAN USERWhat about this? This method will find and save the pivotal element of the original array.
This pivotal element is the last element of the lhs partition. Complexity O(2n)?
int main(int argc, char* argv[])
{
int array[] = {1,2,3,4,5,6,7,8,9};
int size = sizeof(array)/sizeof(int);
int total = 0;
int imbalance = -1;
int pivotal_elem = -1;
split_array(array, size, size, &total, &imbalance, &pivotal_elem);
return 0;
}
int split_array(int* curr_elem,
int curr_size,
int orig_size,
int* total,
int* imbalance,
int* pivotal_elem)
{
int prev_rhs_elems = 0;
*total += *curr_elem;
if (curr_size > 1)
{
prev_rhs_elems = split_array(curr_elem+1, curr_size-1, orig_size, total, imbalance, pivotal_elem);
}
int rhs = *curr_elem + prev_rhs_elems;
int lhs = *total - rhs;
int temp = (rhs > lhs) ? (rhs-lhs) : (lhs-rhs);
if (*imbalance < 0 || *imbalance > temp)
{
*imbalance = temp;
*pivotal_elem = orig_size - curr_size - 1;
}
return *curr_elem;
}
You are correct, any integer reversed twice should be equal to its original value. The reason you are experiencing all these problems is because you are reversing characters of a corresponding string representation of an integer, instead of reversing bits of that integer. If you look at binary representation of 2 (00000010) and truly reverse it to 01000000, you will arrive to decimal 64. Then, if you reverse 64 (01000000) back to 00000010, you will have your decimal 2 back.
- cplusplus January 02, 2010