'Find the maximum number of distinct elements that can be achieved in array a after at most k operations

My assignment:

Consider two arrays a and b where each consists of n integers. In one operation:

  1. Select two indices i and j (0 <= i,j < n)
  2. Swap integers a[i] and b[j]

This operation can be performed at most k times.

Find the maximum number of distinct elements that can be achieved in array a after at most k operations

arraysalgorithmsortingdata-structures


Solution 1:[1]

public class MaxDistFromArray {

    static int count = 0;

    public static void main(String args[]) {

        List<Integer> a = new ArrayList<Integer>(), b = new ArrayList<Integer>();

        a.add(2);
        a.add(3);
        a.add(3);
        a.add(2);
        a.add(2);

        b.add(1);
        b.add(3);
        b.add(2);
        b.add(4);
        b.add(1);

        System.out.println(getMaximumDistinctCount(a, b, 2));

    }

    // 1234
    // 6789

    //
    public static int getMaximumDistinctCount(List<Integer> a, List<Integer> b, int k) {

        int size = a.size();

        List<int[]> arrList = new ArrayList<int[]>();

        for (int i = 0; i < size; i++) {

            for (int j = 0; j < size; j++) {

                int[] arr = new int[2];
                arr[0] = i;
                arr[1] = j;

                arrList.add(arr);
            }
        }

        getMaximumDistinct(arrList, arrList.size(), k, a, b);

        return count;

    }

    static void getMaximumDistinct(List<int[]> arrList, int n, int r, List<Integer> a, List<Integer> b) {
        int data[][] = new int[r][2];
        getMaximum(arrList, data, 0, n - 1, 0, r, a, b);
    }

    static void getMaximum(List<int[]> arrList, int[][] data, int start, int end, int index, int r, List<Integer> a,
            List<Integer> b) {

        if (index == r) {

            List<Integer> aTemp = a;
            List<Integer> bTemp = b;

            for (int[] s2 : data) {
                int an = aTemp.get(s2[0]);
                int bn = bTemp.get(s2[1]);

                aTemp.set(s2[0], bn);
                bTemp.set(s2[1], an);
            }

            Set<Integer> c = new HashSet<>();

            for (int i = 0; i < aTemp.size(); i++) {
                c.add(aTemp.get(i));
            }

            if (count < c.size()) {
                count = c.size();
            }
            return;
        }

        for (int i = start; i <= end && end - i + 1 >= r - index; i++)             {
            data[index] = arrList.get(i);
            getMaximum(arrList, data, i + 1, end, index + 1, r, a, b);
        }

    }
}

Solution 2:[2]

I realized this question was asked in one of my phone interviews at a really big company. I was able to provide a constant time O(n) solution but still got a reject.

Anyway here is the solution in python:

def getMaximumDistinctCount(a, b, k):
    uniquesInA = len(set(a))
    uniquesInB = len(set(b))
    uniquesInA&B = len(set(a + b))

    return min(len(a), min(uniquesInA&B - uniquesInA, k))

Solution 3:[3]

def getMaximumDistinctCount(a, b, k):
    uniquesInA = len(set(a))
    uniquesInB = len(set(b))
    uniquesInA&B = len(set(a + b))
    return min(len(a), min(uniquesInA&B - uniquesInA, k))+ uniquesInA

Solution 4:[4]

def getMaximumDistinctCount(a, b, k):
    lena = len(set(a))
    lena&B = len(set(a + b))
    return min(len(a), min(lena&B - lena, k)+ lena)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 jmoerdyk
Solution 2 P.B.UDAY
Solution 3 Tyler2P
Solution 4 manideep laxmishetty

Related Questions