How to find the duplicate elements in an array (negative numbers) and Round H 2020 Google Kick Start Rugby Problem solved in Java

Duplicate Elements in an Array

For Example: Input : -1 -2 -3 1 -3 -6 6 Duplicate : -3 Original : -1 -2 -3 1 -6 6
Here we have implemented List Interface and Hashtable Collection Framework from util package. It is not necessary to use List Interface instead we can choose any other Interfaces according to how we want our data to be stored or we can direcly print the duplicate numbers directly.

Now, Let me explain how Hashtables works we have to implement Hashtable with atleast two arguments one is for Index as Integer and another one is for our values to be stored in that Index.

Here we have iterated through all the values one by one to check whether the values are present in Hashtable or not. If the value is not in the table we have to insert those values in the Hashtable and if the value is present in the table either we can print the values or omit or to store the data for future use. Now we can print Original values using print statement. Instead of using Numbers we also can use String, Characters as our values.


Java Code

import java.util.*; public class Solution { public static List<Integer> findDuplicates(int[] nums) { Hashtable<Integer,Integer> h = new Hashtable<Integer,Integer>(); List<Integer> list = new ArrayList<Integer>(); for(int i=0; i<nums.length; i++) { if(h.containsValue(nums[i])) { list.add(nums[i]); } else { h.put(i,nums[i]); } } return list; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int a[] = {-1, -2, -3, 1, -3, -6, 6}; System.out.println(findDuplicates(a)); } }


Round H 2020 Kick Start Rugby problem

Problem

On a far away planet, rugby is played in the two dimensional Cartesian coordinate system without bounds. The players can occupy integer grid points only and they can move to the neighboring grid points in any of the four cardinal directions. Specifically, if a player is currently at the point (X, Y), then they can move to either of the points (X+1, Y), (X-1, Y), (X, Y+1), or (X, Y-1) in a single step.

After the game, N players are scattered throughout the coordinate system such that any grid point is empty or occupied by one or more players. They want to gather for a picture and form a perfect horizontal line of N grid points, one player per point, all occupied points next to each other. Formally, the players have to move so as to occupy the grid points (X, Y), (X+1, Y), (X+2, Y), ..., (X+N-1, Y) for some coordinates X and Y. What is the minimum total number of steps the players should make to form a perfect line if they are free to choose the position of the line in the coordinate system and the ordering of players is not important?

Input

The first line of the input gives the number of test cases T. T test cases follow. The first line of each test case gives the number of players N. The subsequent N lines give the initial coordinates of the players. The i-th of these lines contains two integers Xi and Yi, which describe the initial position of i-th player (1 ≤ i ≤ N).

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum total number of steps that the players need to make in order to form a perfect horizontal line.

Limits

Memory limit: 1 GB. 1 ≤ T ≤ 100.

Test Set 1

Time limit: 20 seconds. 1 ≤ N ≤ 10. -500 ≤ Xi ≤ 500. -500 ≤ Yi ≤ 500.

Test Set 2

Time limit: 40 seconds. 1 ≤ N ≤ 105 for at most 10 cases. 1 ≤ N ≤ 104 for the remaining cases. -109 ≤ Xi ≤ 109. -109 ≤ Yi ≤ 109.

Sample

In the first test case, one of many optimal solutions is obtained by the second player moving two steps to the left and three steps down to the point (2, 1).

In the second test case, a perfect line can be formed with a total of four steps if the first player moves to the point (0, 2) and the third player moves to the point (2, 2).

Java Code

import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int test = sc.nextInt(); for(int t=0; t<test; t++) { long n = sc.nextInt(); long a[] = new long[(int) n]; long b[] = new long[(int) n]; for(int i=0; i<n; i++) { a[i] = sc.nextLong(); b[i] = sc.nextLong(); } long add =0; Arrays.sort(b); add += solve(b); Arrays.sort(a); for(long i=0; i<n; i++) { a[(int) i] -= i; } Arrays.sort(a); add += solve(a); System.out.printf("Case #%d: %d\n",t+1,add); } } private static long solve(long[] a) { long mid = a[a.length/2]; long result = 0; for(int i=0; i<a.length; i++) { result += Math.abs(a[i] - mid); } return result; } }

Round H 2020 - Kick Start 2020 Editor. Here you can check whether your code satisfies Time and Space Complexity of the Problem.

Here is the link for Google KickStart Round F 2021 Trash Bins Problem.