Subsequence-Numbers Divisible by 7 solution codechef

Subsequence-Numbers Divisible by 7 solution codechef

Kulyash has given you an array AA of size NN.

He defines the subsequence-number of a non-empty subsequence SS of array AA as the number formed by the concatenation of all the elements of the subsequence SS.

Find the count of non-empty subsequences of AA having their subsequence-numbers divisible by 77. Since the answer can be huge, output it modulo 109+7109+7.

Through this contest, selected students get access to a free 6 month LinkedIn Premium subscription which helps students:

  • Discover & apply to 20M+ jobs/internships on LinkedIn
  • Reach out to hiring managers/recruiters/mentors directly
  • Find career paths that people similar to them have taken
  • Learn from over 17K expert-led LinkedIn Learning courses (technical & soft-skills) with certificates

For example: Consider A=[1,2,3,4,5,6,7,8,9,10]A=[1,2,3,4,5,6,7,8,9,10]. A subsequence SS of AA is [2,5,7,10][2,5,7,10]. The subsequence-number of this subsequence is 2571025710.

Input Format

  • The first line will contain TT, the number of test cases. Then the test cases follow.
  • The first line of each test case contains one integer NN, the size of the array.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN — the elements of the array AA.

Output Format

For each test case, output in a single line the number of subsequences with subsequence-number divisible by 77 modulo 10000000071000000007.

Subsequence-Numbers Divisible by 7 solution codechef

  • 1T10001≤T≤1000
  • 1N31051≤N≤3⋅105
  • 1Ai31051≤Ai≤3⋅105
  • Sum of NN over all test cases does not exceed 31053⋅105

Sample Input 1 

1 2
1 2 3 4
7 7

Sample Output 1 


Subsequence-Numbers Divisible by 7 solution codechef

Test case 11: Only 33 subsequences are possible for the given array. These are [1][1][1,2][1,2], and [2][2]. The subsequence-numbers are 111212, and 22 respectively. None of the subsequence-numbers are divisible by 77, so the answer is 00.

Test case 22: [1,4][1,4] is the only subsequence having its subsequence-number 1414 which is divisible by 77. So, the answer is 11.

Test case 33: All the non-empty subsequences [7][7][7][7], and [7,7][7,7] have their subsequence-numbers 7,7,7,7, and 7777 divisible by 77. So, the answer is 33.


Click here

Subsequence-Numbers Divisible by 7 solution codechef is one of the most asked coding question. This question is repeated in almost every company paper and if you are ready to crack the interviews and the question papers then you must check our website on daily purpose so that you can get the answer of the latest question “Subsequence-Numbers Divisible by 7 solution codechef”.

Leave a Comment