Lexicographical smallest alternate Array

Given two arrays of element between 0 to N- 1 of length N. Find the lexicographically smallest array c such that for any index i  c[i] = ( a[i] + b[i])%N. To find the lexicographically smallest array we can rearrange the elements of the second array.

Example:

Input: 
a[]: {0, 1, 2, 3}
b[]: {3, 1, 0, 2}
Output: 
{0, 0, 0, 0}
Explanation:  
If we  rearrange the array b as {0, 3, 2, 1} then the result array will become the lexicographically smallest. 

Input: 
a[]: {0, 1, 2}
b[]: {1, 1, 2}
Output: 
{1, 0, 0}
Explanation: 
Here, we can get the minimum array by rearranging the b as a {1, 2, 1} and the resultant array will become
{1, 0, 0}.

Approach:
The value of the first array is fixed but we can rearrange the elements of the second array. So first we will check for the sum can be equal to n or zero in both condition the resultant array become the lexicographically smallest. If  it is not the case than we go for the value which produces the smallest remainder. We will get this value by using binary search.

Time Complexity: O(N*log(N))

Below is implementation of the above idea.

#include<bits/stdc++.h>

using namespace std;
#define LL long long

int * findArray(int a[], int b[], int n) {

  multiset < int > s;

  // ceating the result array
  int * c = new int[n];

  // sorting the array b
  for (int i = 0; i < n; ++i) {

    s.insert(b[i]);
  }

  for (int i = 0; i < n; ++i) {
    //cheking for the sum can equal to n 
    // or not 
    auto pos = s.lower_bound(n - a[i]);

    // if sum can not equal to n 
    // then assigning minimum possible
    // no so that the remainder becomes 
    // min
    if (pos == s.end()) pos = s.begin();

    // updating the value
    c[i] = (a[i] + * pos) % n;

    // deleting the used element 
    s.erase(pos);
  }

  return c;
}

//  print the final array
void print(int c[], int n) {

  for (int i = 0; i < n; ++i)
    cout << c[i] << " ";

}

// Driver function
int main() {

  int a[] = {0,1,1};
  int b[] = {1,0,0};

  int n = sizeof(a) / sizeof(a[0]);

  int * c = findArray(a, b, n);

  print(c, n);
}

Output:

0 1 2