Skip to content

Instantly share code, notes, and snippets.

@so77id
Created November 9, 2021 21:47
Show Gist options
  • Save so77id/c4878a311b70e206a8ecfc5292560238 to your computer and use it in GitHub Desktop.
Save so77id/c4878a311b70e206a8ecfc5292560238 to your computer and use it in GitHub Desktop.
Ev2-I1
//el-k-elemento-menor-en-un-abb
//https://www.hackerrank.com/contests/eda-2021-s2-ev2-i1/challenges/el-k-elemento-menor-en-un-abb
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class BinarySearchTreeNode {
public int data;
public BinarySearchTreeNode left;
public BinarySearchTreeNode right;
BinarySearchTreeNode (int nodeData) {
this.data = nodeData;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
public BinarySearchTreeNode root;
public BinarySearchTree() {
this.root = null;
}
public void insertNode(int nodeData) {
this.root = this.insertNode(this.root, nodeData);
}
private BinarySearchTreeNode insertNode(BinarySearchTreeNode root, int nodeData) {
if (root == null) {
root = new BinarySearchTreeNode(nodeData);
} else {
if (nodeData <= root.data) {
root.left = this.insertNode(root.left, nodeData);
} else {
root.right = this.insertNode(root.right, nodeData);
}
}
return root;
}
}
class BinarySearchTreePrintHelper {
public static void printInorder(BinarySearchTreeNode root, String sep, BufferedWriter bufferedWriter) throws IOException {
if (root == null) {
return;
}
BinarySearchTreePrintHelper.printInorder(root.left, sep, bufferedWriter);
if (root.left != null) {
bufferedWriter.write(sep);
}
bufferedWriter.write(String.valueOf(root.data));
if (root.right != null) {
bufferedWriter.write(sep);
}
BinarySearchTreePrintHelper.printInorder(root.right, sep, bufferedWriter);
}
}
class Result {
/*
* Complete the 'kthSmallest' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER_BINARY_SEARCH_TREE root
* 2. INTEGER k
*/
/*
* For your reference:
*
* BinarySearchTreeNode {
* int data;
* BinarySearchTreeNode left;
* BinarySearchTreeNode right;
* }
*
*/
public static int kthSmallest(BinarySearchTreeNode root, int k) {
while(root != null && k > 0) {
if(root.left == null) {
k--;
if(k == 0) {
return root.data;
}
root = root.right;
} else {
BinarySearchTreeNode auxiliar = root.left;
while(auxiliar.right != null && auxiliar.right != root) {
auxiliar = auxiliar.right;
}
if(auxiliar.right == null) {
auxiliar.right = root;
root = root.left;
}
else {
auxiliar.right = null;
k--;
if(k == 0) {
return root.data;
}
root = root.right;
}
}
}
return -1;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
int k = Integer.parseInt(bufferedReader.readLine().trim());
BinarySearchTree root = new BinarySearchTree();
int rootCount = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, rootCount).forEach(i -> {
try {
int rootItem = Integer.parseInt(bufferedReader.readLine().trim());
root.insertNode(rootItem);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
int result = Result.kthSmallest(root.root, k);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
//k-points-closed-to-origin
//https://www.hackerrank.com/contests/eda-2021-s2-ev2-i1/challenges/k-points-closed-to-origin
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'kPointsClosedToOrigin' function below.
*
* The function is expected to return a 2D_INTEGER_ARRAY.
* The function accepts following parameters:
* 1. 2D_INTEGER_ARRAY points
* 2. INTEGER k
*/
public static List<List<Integer>> kPointsClosedToOrigin(List<List<Integer>> points, int k) {
PriorityQueue<List<Integer>> pq = new PriorityQueue<List<Integer>>(points.size(), new Comparator<List<Integer>>() {
public int compare(List<Integer> n1, List<Integer> n2) {
int dist1 = n1.get(0) * n1.get(0) + n1.get(1) * n1.get(1);
int dist2 = n2.get(0) * n2.get(0) + n2.get(1) * n2.get(1);
return dist1 - dist2;
}
});
for(List<Integer> p:points) {
pq.add(p);
}
List<List<Integer>> sol = new ArrayList<List<Integer>>();
while(!pq.isEmpty() && k >0) {
sol.add(pq.poll());
k--;
}
return sol;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(bufferedReader.readLine().trim());
int k = Integer.parseInt(bufferedReader.readLine().trim());
List<List<Integer>> points = new ArrayList<>();
IntStream.range(0, n).forEach(i -> {
try {
points.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
List<List<Integer>> closed = Result.kPointsClosedToOrigin(points, k);
closed.stream()
.map(
r -> r.stream()
.map(Object::toString)
.collect(joining(" "))
)
.map(r -> r + "\n")
.collect(toList())
.forEach(e -> {
try {
bufferedWriter.write(e);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment