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 
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));
	}
}