3
\$\begingroup\$

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 ith line denotes the ticket id of the ith 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();
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The words "from to at" from the task description don't make any sense to me. Could you re-check the whole description? It seems to be incomplete. \$\endgroup\$ – Roland Illig Jan 27 '18 at 11:26
  • 2
    \$\begingroup\$ Oh, and you could fix the indentation of the code so that the review can concentrate on more interesting stuff. \$\endgroup\$ – Roland Illig Jan 27 '18 at 11:27
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

I agree with greybeard’s answer:

"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:"

giving every individual a winning opportunity opposed to having one number match for two tickets would nearly be impossible or would take years to win it finding that matching ticket.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.