CODEWITHSUNDEEP
c++algorithmfor-loopdata-structurestime
surajit das
surajit das

Reputation: 13

Is there any way to merge two (or multiple) for loops to reduce the overall time complexity?

Actually I have solved the problem of comparing results of a calculation and returning the minimum value. Although the I successfully implemented the logic and executed the code finely but failed to reduce the time complexity.

#include<iostream>
#include<algorithm>
#include<climits>

using namespace std;

int checkMinimum(int array[], int index)
{
  int result = INT_MAX;

  for(int i = 0; i < index; ++i)
    for(int j = 0; j < index; ++j)
      if(i != j && (min(result, ((array[i] & array[j]) ^ (array[i] | array[j]))) < result))
        result = min(result, ((array[i] & array[j]) ^ (array[i] | array[j])));

  return result;
}

void getMinimum()
{
  int index;
  cin >> index;
  int array[index];

  for(int i = 0; i < index; ++i)
    cin >> array[i];

  cout << checkMinimum(array, index) << endl;
}

int main()
{
  int limit;
  cin >> limit;
  while(limit--)
    getMinimum();

  return 0;
}

After researching on for loops and trying to merge them together can't help at all because it's hard to fulfil the conditions of the loops into one.

#include<iostream>
#include<algorithm>
#include<climits>

using namespace std;

int checkMinimum(int array[], int index)
{
  int result = INT_MAX;

  for(int i = 0, j = index - 1; i != j; ++i, --j)
    if((min(result, ((array[i] & array[j]) ^ (array[i] | array[j]))) < result))
      result = min(result, ((array[i] & array[j]) ^ (array[i] | array[j])));

  return result;
}

void getMinimum()
{
  int index;
  cin >> index;
  int array[index];

  for(int i = 0; i < index; ++i)
    cin >> array[i];

  cout << checkMinimum(array, index) << endl;
}

int main()
{
  int limit;
  cin >> limit;
  while(limit--)
    getMinimum();

  return 0;
}

So how can I reduce the time complexity of this?

Upvotes: 0

Views: 560

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

(array[i] & array[j]) ^ (array[i] | array[j]) is equivalent to array[i] ^ array[j] (&, ^, | are all bitwise operations; write the truth table for one bit).

To minimize the XOR, the most important thing is that the high-order bits agree. Let's say the input has several numbers 0xxxx and several numbers 1xxxx. There is no point in trying the pairs with a 0xxxx and a 1xxxx; even if the xxxx part is exactly the same, the XOR is 10000, whereas the XOR of any 0xxxx with any 0xxxx, or the XOR of any 1xxxx with any 1xxxx is at most 01111, which is less than 10000.

Repeating this logic within each group at the next bit, and the one after that, it's possible to show that the pair with the minimum XOR appear next to each other in sorted order. Therefore you can sort the array and compute the minimum over n − 1 adjacent pairs.

Upvotes: 3

Related Questions