Cerinta completa

The SuperBowl 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 to at least once.

For example, if there are distinct tickets with ticket ID and , 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 denoting the total number of lottery tickets in the super bowl.
Each of the next lines contains a string, where string on a line denotes the ticket id of the ticket.

Constraints

  • length of
  • sum of lengths of all
  • Each ticket id consists of digits from

Output Format

Print the number of pairs in a new line.

Sample Input 0

5
129300455 
5559948277
012334556 
56789
123456879

Sample Output 0

5

Explanation 0

Pairs of distinct tickets that make for a winning scenario are :

Ticket ID 1 Ticket ID 2 Winning Pair

Notice that each winning pair has digits from to atleast once, and the digits in the ticket ID can be of any order. Thus, the number of winning pairs is .

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            this.in = is;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        String next() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            if (c == -1) return null;
            StringBuilder sb = new StringBuilder();
            while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
            return sb.toString();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();

        long[] freq = new long[1 << 10];
        for (int i = 0; i < n; i++) {
            String s = fs.next();
            int mask = 0;
            for (int j = 0; j < s.length(); j++) {
                mask |= 1 << (s.charAt(j) - '0');
            }
            freq[mask]++;
        }

        long ans = 0;
        int full = (1 << 10) - 1;
        for (int i = 0; i <= full; i++) {
            if (freq[i] == 0) continue;
            for (int j = i; j <= full; j++) {
                if (freq[j] == 0) continue;
                if ((i | j) == full) {
                    if (i == j) {
                        ans += freq[i] * (freq[i] - 1) / 2;
                    } else {
                        ans += freq[i] * freq[j];
                    }
                }
            }
        }

        System.out.println(ans);
    }
}

Scor obtinut: 1.0

Submission ID: 464615214

Link challenge: https://www.hackerrank.com/challenges/winning-lottery-ticket/problem

Winning Lottery Ticket