##### Lucky Number Eight

Source : Hackerrank

Given an n-digit positive integer, count and print the number of 8 multiples of that can be formed by concatenating subsequences of the given number’s digits, modulo 10^9+7.

**Input Format**

The first line contains an integer denoting n.

The second line contains a string describing an n-digit integer.

**Constraints**

1<=n<= 2 x 10^5

**Output Format**

Print a single integer denoting the count of multiples of 8 that can be formed from subsequences of the given number, modulo 10^9+7.

**Sample Input 0**

```
3
968
```

**Sample Output 0**

```
3
```

**Explanation 0**

The numbers obtained from subsequences of 968 are 9,6 ,8 , 96,68 ,98 and 968 . Three of these numbers (i.e.,968 ,96 , and 8) are divisible by 8, so we print the value of 3 mod 10^9+7=3 as our answer.

**Solution**

Solution is partially successfull. I have got 15 points out of 27. Test cases 1, 2, and 3 have Runtime error and 8 is wrong answer. Hint for the solution: 3 888 The first, second and third 8's all all their own 1 digit sub sequences. So they each get counted towards the total. For 888 there are the following sub sequences: 8, 8, 8, 88, 88, 88, 888. Since each is divisible by 8 the answer is 7. Leading 0s also count, so for 808, 08 and 8 are different sub sequences, and both are divisible by 8. 3 800 8, 0, 0, 80, 80, 00, 800 are all the sub sequences and all are divisible by 8, so I think answer will be 7. Comment to get more hints or to discuss the approach.Code:package weekofCode28; import java.util.Scanner; public class LuckyNumberEight { static int printListSubsets(int n, int[] list) { int count = 0; for (int i = 0; i < (1 << n); i++) { int number = 0; for (int j = 0; j < n; j++) { if ((i & (1 << j)) > 0) number = number * 10 + list[j]; } if (number % 8 == 0) count++; } return count - 1; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int size = scan.nextInt(); int n = scan.nextInt(); int k = n; int a[] = new int[size]; int tt = size - 1; while (k != 0) { a[tt] = k % 10; tt--; k = k / 10; } System.out.println(printListSubsets(size, a)); } }