Problemas de Programação

Link to the problem: https://www.hackerrank.com/challenges/bfsshortreach As the name of the problem states, it is necessary to use the Breadth-First Search to solve this problem. Through this approach, it is possible to find the shortest distance from the start node to all the other nodes in the graph.  import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static HashMap<Integer, ArrayList<Integer>> adjList;         public static void bfs(int start, int[] distances) {         Queue<Distance> queue = new ArrayDeque<Distance>();         queue.add(new Distance(start, 0));                 HashSet<Integer> visited = new HashSet<Integer>();                 while (queue.size() > 0) {             Distance curr = queue.poll();             int currNode = curr.node;             int currDistance = curr.distance;                         if (visited.contains(currNode)) {  

Link to the problem: https://www.hackerrank.com/challenges/grid-challenge Since i t is only possible to swap elements in the same row, each row in the input matrix is sorted. Then, it is only necessary to check if every row and column is lexicographically sorted. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                 int numTests = sc.nextInt();         for (int i = 0; i < numTests; i++) {             int n = sc.nextInt();             char[][] matrix = new char[n][n];             for (int j = 0; j < n; j++) {                 String line = sc.next();                 char[] array = line.toCharArray();                 Arrays.sort(array);                 for (int k = 0; k < n; k++) {                     matrix[j][k] = array[k];                 }             }                         boolean not = fals

Link to the problem: https://www.hackerrank.com/contests/womens-codesprint/challenges/mars-and-the-binary-search-tree Using a simple Binary Search Tree could imply in an execution time of O(10^9) in the worst case. Then, a TreeMap structure was used to keep the indexes of the nodes already inserted, which helped to know the location of the new node to be inserted. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static Node root;     public static long mod = (long)Math.pow(10, 9)+7;     public static Node insert(Node n, long value) {         if (root == null) {             root = new Node(null, null, null, value, 1);             return root;         }         else {             Node currNode = n;             Node parentCurrNode = null;             long key = n.key;             while (currNode != null) {                 parentCurrNode = currNode;                                if (currNode.val

Link to the problem: https://www.hackerrank.com/contests/womens-codesprint/challenges/smriti-and-strings For the solution, a stack was used to keep the lexicographically largest characters. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                 int numTests = sc.nextInt();         for (int i = 0; i < numTests; i++) {             String s = sc.next();             int numEliminate = sc.nextInt();                         int count = 0;             Deque<Character> stack = new ArrayDeque<Character>();             for (int j = 0; j < s.length(); j++) {                 while (stack.size() > 0 && stack.peekLast() < s.charAt(j) && count < numEliminate) {                     stack.pollLast();                     count++;                 }                 stack.addLast(s.c

Link to the problem: https://www.hackerrank.com/contests/womens-codesprint/challenges/annual-car-race The problem asks to find the third shortest distance in a graph. The edges are weighted, and therefore, it is a good idea to apply Dijkstra's algorithm. It is necessary to call the Dijkstra method three times. The first two are supposed to find and remove the edges that compose the first and second shortest distances from the source to the destination. Finally, the third call is used to find the answer (the third shortest distance), if it exists. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static HashMap<Integer, ArrayList<Edge>> adjList;     public static ArrayList<ArrayList<Integer>> parents;     public static int[] costs;         public static Comparator<EdgeDijkstra> costComparator = new Comparator<EdgeDijkstra>() {         public int compare(

Link to the problem: https://www.hackerrank.com/contests/womens-codesprint/challenges/grouping-the-items After counting the amount of each digit for each number, we group them in by the frequency of 0-9. Then, the amount of groups is printed, followed by the groups that have the largest size. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int numStrings = sc.nextInt();         String[] strings = new String[numStrings];         for (int i = 0; i < numStrings; i++) {             strings[i] = sc.next();         }                 TreeMap<String, TreeMap<Integer, Integer>> map = new TreeMap<String, TreeMap<Integer, Integer>>();         for (int i = 0; i < numStrings; i++) {             map.put(strings[i], new TreeMap<Integer, Integer>());             TreeMap<Integer, Inte

Link to the problem: https://www.hackerrank.com/contests/womens-codesprint/challenges/consonant-reversal import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                 String vowels = "aeiou";                 int numTests = sc.nextInt();         for (int i = 0; i < numTests; i++) {             String line = sc.next();             int last = line.length()-1;             for (int j = 0; j < line.length(); j++) {                 if (vowels.indexOf(line.charAt(j)) > -1) {                     System.out.print(line.charAt(j));                 }                 else {                     for (int k = last; k >= 0; k--) {                         if (vowels.indexOf(line.charAt(k)) == -1) {                             System.out.print(line.charAt(k));                             last = k-1;             

Link to the problem: https://www.hackerrank.com/contests/womens-codesprint/challenges/even-training This is a problem where all you need to do is to check if the amount of '1's is even or odd. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         int n = in.nextInt();         int sum = 0;         for(int a_i=0; a_i < n; a_i++){             if (in.nextInt() == 1) {                 sum++;             }         }                 if (sum%2 == 0) {             System.out.println("Yes " + sum);         }         else {             System.out.println("No " + sum);         }                     } }

Link to the problem: https://www.hackerrank.com/challenges/the-quickest-way-up The problem asks to find the shortest path from one specific position to another one. However, it does not have any weight associated to the edges, which suggests that the algorithm to be used here is the Breadth-First Search (BFS). import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static HashMap<Integer, ArrayList<Integer>> adjList;     public static HashSet<Integer> startingPoints;     public static int[] dice = {1,2,3,4,5,6};         public static int bfs(int start, int end) {         Queue<Move> queue = new ArrayDeque<Move>();         queue.add(new Move(start, 0));                 HashSet<Integer> visited = new HashSet<Integer>();                 while (queue.size() > 0) {             Move curr = queue.poll();             int currPos = curr.pos;             int currCo

Link to the problem: https://www.hackerrank.com/challenges/connected-cell-in-a-grid The problem asks to find the largest number of connected cells in the matrix. It made me think that given a position in the matrix, I should explore as far as possible in order to find all the numbers '1' connected. This approach is known as Depth-First Search. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static int[][] matrix;     public static boolean[][] visited;     public static int numRows;     public static int numCols;     public static int connectedCells;     public static int[] vi = {-1,-1,-1,0,0,1,1,1};     public static int[] vj = {-1,0,1,-1,1,-1,0,1};         public static void dfs(int currI, int currJ) {         if (currI < 0 || currJ < 0 || currI >= numRows || currJ >= numCols || visited[currI][currJ] || matrix[currI][currJ] == 0) {             return;         }          

Brute Force was used to solve this problem. import java.io.*; import java.util.*; class Main {     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 int numCase = 0;         String line = br.readLine();         while (line != null) {             int numElements = Integer.parseInt(line);             int[] elements = new int[numElements];             line = br.readLine();             String[] s = line.split("\\s");             for (int i = 0; i < numElements; i++) {                 elements[i] = Integer.parseInt(s[i]);             }             long biggestProduct = -1;             for (int i = 0; i < numElements; i++) {                 long product = elements[i];                 if (product > biggestProduct) {                     biggestProduct = product;                 }                 for (int j = i+1; j < numElements; j++) {    

Breadth-First Search was used to solve this problem. import java.io.*; import java.util.*; class Main {     public static char[][] matrix;     public static boolean[][] visited;     public static int vi[] = {-1,-1,-1,0,0,1,1,1};     public static int vj[] = {-1,0,1,-1,1,-1,0,1};         public static int bfs(int row, int col, int numRows, int numCols) {         Queue<Coord> queue = new ArrayDeque<Coord>();         queue.add(new Coord(row, col, 1));                 while (queue.size() > 0) {             Coord curr = queue.poll();             int currRow = curr.row;             int currCol = curr.col;             int currSizeSide = curr.sizeSide;                         if (visited[currRow][currCol]) {                 continue;             }             visited[currRow][currCol] = true;                         for (int i = 0; i < 8; i++) {                 int nextRow = currRow+vi[i];                 int nextCol = currCol+vj[i];                 if (nextRow < 0 || n

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static long fibo(long num) {         long next1 = 1;         long next2 = 1;         long sumEven = 0;         for (int i = 2; i <= num; i++) {             long next = next1 + next2;             if (next%2 == 0 && next < num) {                 sumEven += next;             }             if (next > num) {                 return sumEven;             }             next1 = next2;             next2 = next;         }                 return sumEven;     }         public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                 int numTests = sc.nextInt();         for (int i = 0; i < numTests; i++) {             long n = sc.nextLong();             long sum = fibo(n);             System.out.println(sum);         }     } }

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static boolean isPrime(int num) {         for (int i = 2; i < num; i++) {             if (num%i == 0) {                 return false;             }         }                 return true;     }         public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                 int numTests = sc.nextInt();         for (int i = 0; i < numTests; i++) {             int n = sc.nextInt();             ArrayList<Integer> prime = new ArrayList<Integer>();             for (int j = 2; j <= n; j++) {                 if (isPrime(j)) {                     prime.add(j);                 }             }             int mult = 1;             for (int j = 0; j < prime.size(); j++) {                 long max = 0;                 long power = 1;                 for (int k = 1; k < 10; k++) {                     power =

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {         public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         String s = sc.next();                 boolean changed;         do {             changed = false;             StringBuilder sb = new StringBuilder();             for (int i = 0; i < s.length(); i++) {                 if ((i+1) < s.length() && s.charAt(i+1) == s.charAt(i)) {                     i++;                     changed = true;                 }                 else {                     sb.append(s.charAt(i));                 }             }             s = sb.toString();         } while (changed);                         if (s.length() > 0) {             System.out.println(s);         }         else {             System.out.println("Empty String");         }     } }

Breadth-First Search was used to solve this problem. import java.io.*; import java.util.*; class Main {     public static int[][] matrix;     public static boolean[][] visited;     public static int[] vi = {-1,0,0,1};     public static int[] vj = {0,-1,1,0};         public static int bfs(int row, int col, int size) {         Queue<Coord> queue = new ArrayDeque<Coord>();         queue.add(new Coord(row, col, 0));                 while (queue.size() > 0) {             Coord curr = queue.poll();             int currRow = curr.row;             int currCol = curr.col;             int currSteps = curr.steps;                         if (visited[currRow][currCol]) {                 continue;             }             visited[currRow][currCol] = true;                         if (matrix[currRow][currCol] == 3) {                 return currSteps;             }                         for (int i = 0; i < 4; i++) {                 int nextRow = currRow+vi[i];                 in

Brute Force was used to solve this problem. First, all the possible speeds to pass each signal are checked. Those speeds that are common among all the signals are part of the final answer. Finally, the output is processed to be presented. import java.io.*; import java.util.*; class Main {     public static void process() throws NumberFormatException, IOException {           Scanner sc = new Scanner(System.in);                 int numCase = 0;         int numSignals = sc.nextInt();         while (numSignals != -1) {             if (numSignals == 0) {                 System.out.println("Case " + ++numCase + ": 30-60");             }             else {                 ArrayList<HashSet<Integer>> time = new ArrayList<HashSet<Integer>>();                 for (int i = 0; i < numSignals; i++) {                     time.add(new HashSet<Integer>());                 }                                 // check possible speeds for each signa