|
Given an array arr[] of n elements, find the Kth lexicographically smallest in its corresponding cross-product array. For an array arr of n elements, the cross product of the array, cp_arr, is defined as cp_arr = {{arr[i], arr[j}} for all 0 < i, j < n.
Examples:
Input: n = 3, K = 7, arr[] = {3, 1, 2}
Output: [3, 1]
Explanation: [3, 1, 2] * [3, 1, 2] = [ [3, 3], [ 3, 1], [3, 2], [1, 3], [1, 1], [1, 2], [2, 3], [2, 1], [2, 2] ], now sort this cross product array to get the lexicographically increasing order. [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] (in sorted order), so 7th is [3, 1]
Input: n = 4, K = 13, arr = {1, 7, 3, 1}
Output: [7, 1]
Explanation: [1, 7, 3, 1] * [1, 7, 3, 1] = [ [1, 1], [1, 7], [1, 3], [1, 1], [7, 1], [7, 7], [7, 3], [7, 1], [3, 1], [3, 7], [3, 3], [3, 1], [1, 1], [ 1, 7], [1, 3], [1, 1] ], now sort this cross product array to get the lexicographically increasing order. [[1, 1], [1, 1], [1, 1], [1, 1], [1, 3], [1, 3], [1, 7], [1, 7], [3, 1], [3, 1], [3, 3], [3, 7], [7, 1], [7, 1], [7, 3], [7, 7]] (in sorted order) so 13th element is [7, 1].
Approach: To solve the problem follow the below idea:
- The approach is pretty simple we make an array which have all the unique integers array and also has a record of their frequencies and calculate how many pairs are there from each unique integer using their freq i.e. pairs with the first integer as x = freq[x]*n from the sorted array
- If this count is > K value then find the second integer else subtract the number of pairs with x from K to get the correct first element
- To get the second integer divide the leftover K by the freq of x and what even is left over that index element from the sorted array is the second element as we need to return the answer lexicographically, A bit more explanation is given if the freq is more than one repeated number of pairs will occur before proceeding to next integers so this value is calculated.
Follow the below steps to implement the above approach:
- Make an array and put all unique numbers over there
- Make an unordered_map to keep an check on frequency
- Now iterate over the new array and check how to many pairs starting with current element lets call it temp
- Subtract this number from temp from K till K>temp
- Else proceed to find the second integer
- To find the second integer divide left over K_count with freq of current element and find the index, then arr[index] is the output
Implementation of the above approach:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
pair<int, int> func(int n, vector<int> arr, int k)
{
vector<int> b;
b.reserve(n);
unordered_map<int, long> freq;
for (int i = 0; i < n; i++) {
if (!freq.count(arr[i])) {
b.push_back(arr[i]);
}
freq[arr[i]]++;
}
sort(b.begin(), b.end());
sort(arr.begin(), arr.end());
long long count = k;
int x1, x2;
int sz = b.size();
for (int i = 0; i < sz; i++) {
long long temp = freq[b[i]] * n;
if (count <= temp) {
x1 = b[i];
long long temp1 = count;
long long hk = (temp1 / freq[b[i]])
- (temp1 % freq[b[i]] == 0);
hk = max((long long)0, hk);
x2 = arr[hk];
break;
}
else {
count -= temp;
}
}
return { x1, x2 };
}
int main()
{
vector<int> vec = { 3, 1, 2 };
int n = vec.size();
auto x = func(n, vec, 7);
cout << x.first << " " << x.second << endl;
return 0;
}
|
Java
import java.util.*;
import java.util.AbstractMap.SimpleEntry;
public class Main {
public static SimpleEntry<Integer, Integer> func(int n, List<Integer> arr, int k) {
ArrayList<Integer> b = new ArrayList<>();
HashMap<Integer, Long> freq = new HashMap<>();
for (int i = 0; i < n; i++) {
if (!freq.containsKey(arr.get(i))) {
b.add(arr.get(i));
}
freq.put(arr.get(i), freq.getOrDefault(arr.get(i), 0L) + 1);
}
Collections.sort(b);
Collections.sort(arr);
long count = k;
int x1 = 0, x2 = 0;
int sz = b.size();
for (int i = 0; i < sz; i++) {
long temp = freq.get(b.get(i)) * n;
if (count <= temp) {
x1 = b.get(i);
long temp1 = count;
long hk = (temp1 / freq.get(b.get(i))) - (temp1 % freq.get(b.get(i)) == 0 ? 1 : 0);
hk = Math.max(0L, hk);
x2 = arr.get((int) hk);
break;
}
else {
count -= temp;
}
}
return new SimpleEntry<>(x1, x2);
}
public static void main(String[] args) {
List<Integer> vec = Arrays.asList(3, 1, 2);
int n = vec.size();
SimpleEntry<Integer, Integer> x = func(n, vec, 7);
System.out.println(x.getKey() + " " + x.getValue());
}
}
|
Python
def func(n, arr, k):
b = []
freq = {}
for i in range(n):
if arr[i] not in freq:
b.append(arr[i])
freq[arr[i]] = freq.get(arr[i], 0) + 1
b.sort()
arr.sort()
count = k
x1, x2 = 0, 0
sz = len(b)
for i in range(sz):
temp = freq[b[i]] * n
if count <= temp:
x1 = b[i]
temp1 = count
hk = temp1 // freq[b[i]] - (temp1 % freq[b[i]] == 0)
hk = max(0, hk)
x2 = arr[hk]
break
else:
count -= temp
return (x1, x2)
vec = [3, 1, 2]
n = len(vec)
x = func(n, vec, 7)
print(x[0], x[1])
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static Tuple<int, int> Func(int n, List<int> arr, int k)
{
List<int> b = new List<int>();
Dictionary<int, int> freq = new Dictionary<int, int>();
for (int i = 0; i < n; i++)
{
if (!freq.ContainsKey(arr[i]))
{
b.Add(arr[i]);
}
freq[arr[i]] = freq.ContainsKey(arr[i]) ? freq[arr[i]] + 1 : 1;
}
b.Sort();
arr.Sort();
int count = k;
int x1 = 0, x2 = 0;
int sz = b.Count;
for (int i = 0; i < sz; i++)
{
int temp = freq[b[i]] * n;
if (count <= temp)
{
x1 = b[i];
int temp1 = count;
int hk = temp1 / freq[b[i]] - (temp1 % freq[b[i]] == 0 ? 1 : 0);
hk = Math.Max(0, hk);
x2 = arr[hk];
break;
}
else
{
count -= temp;
}
}
return new Tuple<int, int>(x1, x2);
}
static void Main()
{
List<int> vec = new List<int> { 3, 1, 2 };
int n = vec.Count;
Tuple<int, int> x = Func(n, vec, 7);
Console.WriteLine(x.Item1 + " " + x.Item2);
}
}
|
Javascript
function findPair(n, arr, k) {
let b = [];
let freq = new Map();
for (let i = 0; i < n; i++) {
if (!freq.has(arr[i])) {
b.push(arr[i]);
}
freq.set(arr[i], (freq.get(arr[i]) || 0) + 1);
}
b.sort((a, b) => a - b);
arr.sort((a, b) => a - b);
let count = k;
let x1, x2;
let sz = b.length;
for (let i = 0; i < sz; i++) {
let temp = freq.get(b[i]) * n;
if (count <= temp) {
x1 = b[i];
let temp1 = count;
let hk = Math.floor(temp1 / freq.get(b[i])) - (temp1 % freq.get(b[i]) === 0 ? 1 : 0);
hk = Math.max(0, hk);
x2 = arr[hk];
break;
}
else {
count -= temp;
}
}
return [x1, x2];
}
let vec = [3, 1, 2];
let n = vec.length;
let x = findPair(n, vec, 7);
console.log(x[0], x[1]);
|
Time Complexity: O(N)
Auxiliary Space: O(N)
|
