Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Count all subsequences having product less than K

Revision en1, by wish_me, 2017-10-08 11:46:59

Given a non negative array, find the number of subsequences having product smaller than K.

k<10^2 arr.size<10^3

Examples:

Input : [1, 2, 3, 4]

k = 10

Output :11

The subsequences are {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}

Input : [4, 8, 7, 2]

k = 50

Output : 9

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English wish_me 2017-10-08 11:46:59 403 Initial revision (published)