trjhtr

I was trying to solve one of the hackerrank practice questions. Could anyone please let me know how can I make this code much effective, in terms of time and space complexity?

The Super Bowl Lottery is about to commence, and there are several
lottery tickets being sold, and each ticket is identified with a
ticket ID. In one of the many winning scenarios in the Superbowl
lottery, a winning pair of tickets is:

• Concatenation of the two ticket IDs in the pair, in any order,
  contains each digit from 0 to 9 at least once.

For example, if there are 2 distinct tickets with ticket ID 12930455 and 56789, (129300455, 56789) is a winning pair.

NOTE: The ticket IDs can be concantenated in any order. Digits in the
ticket ID can occur in any order.

Your task is to find the number of winning pairs of distinct tickets,
such that concatenation of their ticket IDs (in any order) makes for a
winning scenario. Complete the function winningLotteryTicket which
takes a string array of ticket IDs as input, and return the number of
winning pairs.

Input Format

The first line contains n denoting the total number of lottery tickets
in the Super Bowl. Each of the next n lines contains a string, where
string on a i^th line denotes the ticket id of the i^th ticket.

Constraints

• [1 ≤ pretty much everything input ≤ 10⁶]


• Each ticket id consists of digits from [0, 9]

Output Format

Print the number of pairs in a new line.

Sample Input

5 
129300455 
5559948277 
012334556 
56789 
123456879 

Sample Output

5

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution 
 static Long winningLotteryTicket(String tickets) 
 int count = 0;
 for(int i = 0 ; i < tickets.length-1 ; i++) 
 for(int j = i+1 ; j < tickets.length ;j++ )
 if(!(tickets[i]).equals(tickets[j]) && getStatus(tickets[i],tickets[j]))
 count++;
 
 
 
 return Long.valueOf(count);
 

 public static boolean getStatus(String a, String b)
 String c = a+b;
 if(c.length() < 10)
 return false;
 
 Set<Character> charSet = new HashSet<>();
 char arr = c.toCharArray();
 for(int i = 0; i < arr.length; i++)
 charSet.add(arr[i]);
 

 if (charSet.size() == 10)
 return true;
 else 
 return false;
 
 

 public static void main(String args) 
 Scanner in = new Scanner(System.in);
 int n = in.nextInt();
 String tickets = new String[n];
 for(int tickets_i = 0; tickets_i < n; tickets_i++)
 tickets[tickets_i] = in.next();
 
 Long result = winningLotteryTicket(tickets);
 System.out.println(result);
 in.close();
 

try-with-resources

Since Java 7, you can use try-with-resources for safe and efficient handling of the underlying I/O resource.

return boolean

if (condition) 
 return true;
 else 
 return false;

This kind of code can be simplified as return condition.

Method names

Your naming can be better refined to reflect what they are doing. For example, getStatus can be renamed as hasUniqueNumerals, following the standard is/has prefix for methods returning a boolean. winningLotteryTicket can be renamed as countWinningPairs.

for-each loop

Your loop on c.toCharArray() can also be written as:

for (char current : c.toCharArray()) 
 charSet.add(current);

What's nice

• You checked if the concatenation of the two inputs will give you 10 or more digits, returning false first if not.




• You declared charSet as a Set rather than a HashSet and relied on generic type inference.

Listless additions to h.j.k.'s answer:

• no doc comments
  


• the name getStatus() is not hinting in a useful direction


• the number of winning pairs may easily exceed Integer.MAX_VALUE
  
  (there may have been a reason for Long)

code alternative for getStatus() without concatenation, with one more early out:

/** Adds <code>char</code>s from <code>a</code> to <code>charSet</code>
 * @return size of the resulting <code>Set&lt;Character></code> */
static int accumulateChars(Set<Character> charSet, String a) 
 for (char c: a.toCharArray())
 charSet.add(c);
 return charSet.size();


static boolean all10(final String a, final String b) 
 if (a.length()+b.length() < 10)
 return false;
 final Set<Character> charSet = new HashSet<>();
 return accumulateChars(charSet, a) <= 10
 && 10 == accumulateChars(charSet, b);

In each iteration of winningLotteryTicket()'s outer loop, tickets[i] stays the same for all the iterations of the inner loop, as does its contribution to the set.

If you didn't literally concatenate strings, it was apparent that the same sets were created for the 2nd ticket's digits time and again - and the sets "checked for completeness" were the unions of the digit/char sets of tickets i and j:

It looks advantageous to create each ticket's set once and for all and think hard about what can be done to reduce the number of set unions to evaluate - if ticket i consists of 2 distinct digits, only, there's no need to pair with any ticket consisting of no more than 7 distinct digits.

If one ticket contains every digit, it is a winner paired with every other ticket …

If and when coding that proves not fast enough, note that the digit sets are quite small and reconsider their representation.