# HackerRank : Week of Code 28 – Lucky Number Eight

By | January 12, 2017
##### 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
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));
}
}