Find the lexicographically smallest sequence which can be formed by re-arranging elements of second array

0 0 8 minutes read

Given two arrays A and B of N integers. Reorder the elements of B in itself in such a way that the sequence formed by (A[i] + B[i]) % N after re-ordering is the smallest lexicographically. The task is to print the lexicographically smallest sequence possible.
Note: The array elements are in range [0, n).
Examples:

Input: a[] = {0, 1, 2, 1}, b[] = {3, 2, 1, 1}
Output: 1 0 0 2
Reorder B to {1, 3, 2, 1} to get the smallest sequence possible.
Input: a[] = {2, 0, 0}, b[] = {1, 0, 2}
Output: 0 0 2

Approach: The problem can be solved greedily. Initially keep a count of all the numbers of array B using hashing, and store them in the set in C++, so that lower_bound() [ To check for an element ] and erase() [ To erase an element ] operations can be done in logarithmic time.
For every element in the array, check for a number equal or greater than n-a[i] using lower_bound function. If there are no such elements then take the smallest element in the set. Decrease the value by 1 in the hash table for the number used, if the hash table’s value is 0, then erase the element from the set also.
However there is an exception if the array element is 0, then check for 0 at the first then for N, if both of them are not there, then take the smallest element.
Below is the implementation of the above approach:

CPP

// C++ implementation of the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to get the smallest
// sequence possible
void solve(int a[], int b[], int n)
{
 
    // Hash-table to count the
    // number of occurrences of b[i]
    unordered_map<int, int> mpp;
 
    // Store the element in sorted order
    // for using binary search
    set<int> st;
 
    // Iterate in the B array
    // and count the occurrences and
    // store in the set
    for (int i = 0; i < n; i++) {
        mpp[b[i]]++;
        st.insert(b[i]);
    }
 
    vector<int> sequence;
 
    // Iterate for N elements
    for (int i = 0; i < n; i++) {
 
        // If the element is 0
        if (a[i] == 0) {
 
            // Find the nearest number to 0
            auto it = st.lower_bound(0);
            int el = *it;
            sequence.push_back(el % n);
 
            // Decrease the count
            mpp[el]--;
 
            // Erase if no more are there
            if (!mpp[el])
                st.erase(el);
        }
 
        // If the element is other than 0
        else {
 
            // Find the difference
            int x = n - a[i];
 
            // Find the nearest number which can give us
            // 0 on modulo
            auto it = st.lower_bound(x);
 
            // If no such number occurs then
            // find the number closest to 0
            if (it == st.end())
                it = st.lower_bound(0);
 
            // Get the number
            int el = *it;
 
            // store the number
            sequence.push_back((a[i] + el) % n);
 
            // Decrease the count
            mpp[el]--;
 
            // If no more appears, then erase it from set
            if (!mpp[el])
                st.erase(el);
        }
    }
 
    for (auto it : sequence)
        cout << it << " ";
}
 
// Driver Code
int main()
{
    int a[] = { 0, 1, 2, 1 };
    int b[] = { 3, 2, 1, 1 };
    int n = sizeof(a) / sizeof(a[0]);
    solve(a, b, n);
    return 0;
}

Java

// Java implementation of the
// above approach
import java.util.*;
 
class GFG 
{
 
  // Function to get the smallest
  // sequence possible
  static void solve(int[] a, int[] b, int n)
  {
 
    // Hash-table to count the
    // number of occurrences of b[i]
    HashMap<Integer, Integer> mpp
      = new HashMap<Integer, Integer>();
 
    // Store the element in sorted order
    // for using binary search
    HashSet<Integer> st = new HashSet<Integer>();
 
    // Iterate in the B array
    // and count the occurrences and
    // store in the set
    for (int i = 0; i < n; i++) {
      if (!mpp.containsKey(b[i]))
        mpp.put(b[i], 0);
      mpp.put(b[i], 1 + mpp.get(b[i]));
      st.add(b[i]);
    }
 
    ArrayList<Integer> sequence = new ArrayList<Integer>();
 
    // Iterate for N elements
    for (int y = 0; y < n; y++) {
      int it = st.size();
      ArrayList<Integer> st1 = new ArrayList<Integer>();
      for (int elem : st) st1.add(elem);
      Collections.sort(st1);
      Collections.reverse(st1);
 
      // If the element is 0
      if (a[y] == 0) {
 
        // Find the nearest number to 0
        it = st.size();
        for (var i = 0; i < st1.size(); i++) {
          if (st1.get(i) >= 0)
            it = i;
        }
        int el = st1.get(it);
        sequence.add(el % n);
 
        // Decrease the count
        if (!mpp.containsKey(el))
          mpp.put(el, 0);
        mpp.put(el, mpp.get(el) - 1);
 
        // Erase if no more are there
        if (mpp.get(el) == 0)
          st.remove(el);
      }
 
      // If the element is other than 0
      else {
 
        // Find the difference
        int x = n - a[y];
 
        // Find the nearest number which can give us
        // 0 on modulo
 
        it = st.size();
        for (int i = 0; i < st1.size(); i++) {
          if (st1.get(i) >= x)
            it = i;
        }
 
        // If no such number occurs then
        // find the number closest to 0
        if (it == st.size()) {
          for (int i = 0; i < st1.size(); i++) {
            if (st1.get(i) >= 0)
              it = i;
          }
        }
 
        // Get the number
        int el = st1.get(it);
 
        // store the number
        sequence.add((a[y] + el) % n);
 
        // Decrease the count
        if (!mpp.containsKey(el))
          mpp.put(el, 0);
        mpp.put(el, mpp.get(el) - 1);
 
 
        // If no more appears, then erase it from
        // set
        if (mpp.get(el) == 0)
          st.remove(el);
      }
    }
 
    for (int elem : sequence)
      System.out.print(elem + " ");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] a = { 0, 1, 2, 1 };
    int[] b = { 3, 2, 1, 1 };
    int n = a.length;
    solve(a, b, n);
  }
}
 
// This code is contributed by phasing17

Python3

# Python3 implementation of the
# above approach
 
# Function to get the smallest
# sequence possible
def solve(a, b, n):
 
    # Hash-table to count the
    # number of occurrences of b[i]
    mpp = dict();
 
    # Store the element in sorted order
    # for using binary search
    st = set()
 
    # Iterate in the B array
    # and count the occurrences and
    # store in the set
    for i in range(len(b)):
        if b[i] not in mpp:
            mpp[b[i]] = 0
         
        mpp[b[i]] += 1;
        st.add(b[i]);
     
 
    sequence = [];
 
    # Iterate for N elements
    for y in range(n):
        it = len(st);
        st1 = sorted(st)
        st1 = st1[::-1]
 
        # If the element is 0
        if (a[y] == 0) :
 
            # Find the nearest number to 0
            it = len(st1)
            for i in range(len(st1)):
 
                if (st1[i] >= 0):
                    it = i;
             
            el = st1[it]
            sequence.append(el % n);
 
            # Decrease the count
            if el not in mpp:
                mpp[el] = 0
            mpp[el] -= 1;
 
            # Erase if no more are there
            if (mpp[el] == 0):
                st.discard(el);
         
 
        # If the element is other than 0
        else :
 
            # Find the difference
            x = n - a[y];
 
            # Find the nearest number which can give us
            # 0 on modulo
             
            it = len(st)
            for i in range(len(st1)):
 
                if (st1[i] >= x):
                    it = i;
             
             
            # If no such number occurs then
            # find the number closest to 0
            if (it == len(st)):
             
                for i in range(len(st1)):
 
                    if (st1[i] >= 0):
                        it = i;
                 
             
 
            # Get the number
            el = st1[it];
             
            # store the number
            sequence.append((a[y] + el) % n);
 
            # Decrease the count
            if el not in mpp:
                mpp[el] = 0;
            mpp[el]-=1;
 
            # If no more appears, then erase it from set
            if (mpp[el] == 0):
                st.remove(el);
 
    print(*sequence)
 
# Driver Code
a = [ 0, 1, 2, 1 ];
b = [ 3, 2, 1, 1 ];
n =  len(a);
solve(a, b, n)
 
# This code is contributed by phasing17

C#

// C# implementation of the
// above approach
 
using System;
using System.Collections.Generic;
 
class GFG {
    // Function to get the smallest
    // sequence possible
    static void solve(int[] a, int[] b, int n)
    {
 
        // Hash-table to count the
        // number of occurrences of b[i]
        Dictionary<int, int> mpp
            = new Dictionary<int, int>();
 
        // Store the element in sorted order
        // for using binary search
        HashSet<int> st = new HashSet<int>();
 
        // Iterate in the B array
        // and count the occurrences and
        // store in the set
        for (int i = 0; i < n; i++) {
            if (!mpp.ContainsKey(b[i]))
                mpp[b[i]] = 0;
            mpp[b[i]]++;
            st.Add(b[i]);
        }
 
        List<int> sequence = new List<int>();
 
        // Iterate for N elements
        for (int y = 0; y < n; y++) {
            int it = st.Count;
            List<int> st1 = new List<int>();
            foreach(int elem in st) st1.Add(elem);
            st1.Sort();
            st1.Reverse();
 
            // If the element is 0
            if (a[y] == 0) {
 
                // Find the nearest number to 0
                it = st.Count;
                for (var i = 0; i < st1.Count; i++) {
                    if (st1[i] >= 0)
                        it = i;
                }
                int el = st1[it];
                sequence.Add(el % n);
 
                // Decrease the count
                if (!mpp.ContainsKey(el))
                    mpp[el] = 0;
                mpp[el]--;
 
                // Erase if no more are there
                if (mpp[el] == 0)
                    st.Remove(el);
            }
 
            // If the element is other than 0
            else {
 
                // Find the difference
                int x = n - a[y];
 
                // Find the nearest number which can give us
                // 0 on modulo
 
                it = st.Count;
                for (var i = 0; i < st1.Count; i++) {
                    if (st1[i] >= x)
                        it = i;
                }
 
                // If no such number occurs then
                // find the number closest to 0
                if (it == st.Count) {
                    for (int i = 0; i < st1.Count; i++) {
                        if (st1[i] >= 0)
                            it = i;
                    }
                }
 
                // Get the number
                int el = st1[it];
 
                // store the number
                sequence.Add((a[y] + el) % n);
 
                // Decrease the count
                if (!mpp.ContainsKey(el))
                    mpp[el] = 0;
                mpp[el]--;
 
                // If no more appears, then erase it from
                // set
                if (mpp[el] == 0)
                    st.Remove(el);
            }
        }
 
        foreach(int elem in sequence)
            Console.Write(elem + " ");
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] a = { 0, 1, 2, 1 };
        int[] b = { 3, 2, 1, 1 };
        int n = a.Length;
        solve(a, b, n);
    }
}
 
// This code is contributed by phasing17

Javascript

// JS implementation of the
// above approach
 
// Function to get the smallest
// sequence possible
function solve(a, b, n)
{
 
    // Hash-table to count the
    // number of occurrences of b[i]
    let mpp = {};
 
    // Store the element in sorted order
    // for using binary search
    let st = new Set();
 
    // Iterate in the B array
    // and count the occurrences and
    // store in the set
    for (var i = 0; i < n; i++) {
        if (!mpp.hasOwnProperty(b[i]))
            mpp[b[i]] = 0;
        mpp[b[i]]++;
        st.add(b[i]);
    }
 
    let sequence = [];
 
    // Iterate for N elements
    for (var y = 0; y < n; y++) {
        let it = st.size;
        let st1 = Array.from(st);
        st1.sort(function(a, b) { return a < b})
         
 
        // If the element is 0
        if (a[y] == 0) {
 
            // Find the nearest number to 0
            it = st.size
            for (var i = 0; i < st1.length; i++)
            {
                if (st1[i] >= 0)
                    it = i;
            }
            let el = st1[it]
            sequence.push(el % n);
 
            // Decrease the count
            if (!mpp.hasOwnProperty(el))
                mpp[el] = 0
            mpp[el]--;
 
            // Erase if no more are there
            if (mpp[el] == 0)
                st.delete(el);
        }
 
        // If the element is other than 0
        else {
 
            // Find the difference
            let x = n - a[y];
 
            // Find the nearest number which can give us
            // 0 on modulo
             
            it = st.size
            for (var i = 0; i < st1.length; i++)
            {
                if (st1[i] >= x)
                    it = i;
            }
             
            // If no such number occurs then
            // find the number closest to 0
            if (it == st.size)
            {
                for (var i = 0; i < st1.length; i++)
                {
                    if (st1[i] >= 0)
                        it = i;
                }
            }
 
            // Get the number
            let el = st1[it];
             
            // store the number
            sequence.push((a[y] + el) % n);
 
            // Decrease the count
            if (!mpp.hasOwnProperty(el))
                mpp[el] = 0;
            mpp[el]--;
 
            // If no more appears, then erase it from set
            if (mpp[el] == 0)
                st.delete(el);
        }
    }
 
    console.log(sequence)
}
 
// Driver Code
let a = [ 0, 1, 2, 1 ];
let b = [ 3, 2, 1, 1 ];
let n = a.length;
solve(a, b, n)
 
// This code is contributed by phasing17

Output:

1 0 0 2

Time Complexity: O(n)

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!