This problem was asked in recent CodeNation Online Test↵
↵
Given A,B,C — Count the number of valid arrays of size "A" — such that each number of the array is in the range [1,C] — and no subarray of length > B exists in the valid array such that all elements of that subarray are equal ↵
↵
1<=A<=10^9↵
↵
1<=B<=50 ↵
↵
1<=C<=10^5↵
↵
↵
A = 3 ↵
↵
B = 1↵
↵
C = 3 ↵
↵
↵
O/Putput — 12 ↵
↵
[121], [123], [131], [132], [213], [212], [231], [232], [312], [313], [321], [323] are all valid arrays. ↵
↵
Idea = Valid Arrays = Total — Invalid arrays = Counting of Invalid Arrays is easier than valid arrays as far as I can conclude. ↵
↵
↵
↵
Given A,B,C — Count the number of valid arrays of size "A"
↵
1<=A<=10^9↵
↵
1<=B<=50 ↵
↵
1<=C<=10^5↵
↵
↵
A = 3 ↵
↵
B = 1↵
↵
C = 3 ↵
↵
↵
O
↵
[121], [123], [131], [132], [213], [212], [231], [232], [312], [313], [321], [323] are all valid arrays. ↵
↵
Idea = Valid Arrays = Total — Invalid arrays = Counting of Invalid Arrays is easier than valid arrays as far as I can conclude. ↵
↵
↵
