--- title: Subsets with MEX in Range | daily.dev description: This explains an algorithm to count subsets of an array whose MEX falls within a range [l, r], returning the result modulo 10^9+7. Instead of generating all... canonical: https://daily.dev/posts/subsets-with-mex-in-range-ktbtrxn7n twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: Subsets with MEX in Range | daily.dev og:description: This explains an algorithm to count subsets of an array whose MEX falls within a range [l, r], returning the result modulo 10^9+7. Instead of generating all... og:url: https://daily.dev/posts/subsets-with-mex-in-range-ktbtrxn7n og:image: https://api.daily.dev/og/posts/kTBTrXN7n.png og:image:alt: Subsets with MEX in Range og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # Subsets with MEX in Range **[C\# Corner](https://daily.dev/sources/csharpcorner)** · 10 min read · 0 upvotes · 0 comments ## Summary This explains an algorithm to count subsets of an array whose MEX falls within a range [l, r], returning the result modulo 10^9+7. Instead of generating all 2^n subsets, it uses value frequencies: for a subset to have MEX = k, every value below k must appear at least once (2^freq[x] - 1 ways), k must be absent (1 way), and values above k are free (2^freq ways). A running product lets every MEX from 0 to r be computed incrementally in O(n + r) time and O(n) space, with a Java implementation provided. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### How do I count subsets of an array whose MEX falls within a given range [l, r] efficiently? Use frequency counting instead of generating subsets. For each candidate MEX value k, every number from 0 to k-1 must appear at least once, contributing 2^freq[x]-1 ways each; k itself must be absent (1 way); and numbers greater than k are optional, contributing 2^count ways. Multiply these together and sum over k in [l, r], computing modulo 10^9+7, for O(n+r) time. _Developers tackling subset-counting problems can save similar combinatorial breakdowns on daily.dev for quick reference._ ### What is the formula for counting subsets with an exact MEX value of k? The count equals the product of (2^freq[x] - 1) for every value x from 0 to k-1, times 2 raised to the number of elements greater than k. Values below k must each appear at least once, the value k must be completely excluded, and values above k can be freely included or excluded, giving the combinatorial total for that exact MEX. _Anyone preparing combinatorics-heavy interview problems can keep formulas like this handy via daily.dev._ ### Why can't you just use 2^freq[x] instead of 2^freq[x]-1 when a value is required to be in a subset? Because 2^freq[x] counts every combination of that value's occurrences including selecting none of them, which violates the requirement that the value must appear at least once. Subtracting 1 removes the all-unselected case, leaving exactly the combinations where at least one occurrence is chosen, for example 2^3-1=7 ways when there are 3 copies of a required value. _Developers debugging off-by-one combinatorics errors can reference worked examples like this on daily.dev._ ## Similar posts on daily.dev - [Mastering "Triplets with Sum in Range": An Efficient Java Approach](https://daily.dev/posts/mastering-triplets-with-sum-in-range-an-efficient-java-approach-62tp1iw6r) · C\# Corner · 1 upvotes · 0 comments - [Erdős Problem \#124](https://daily.dev/posts/erd-s-problem-124-5h47gaso9) · Hacker News · 1 upvotes · 0 comments - [MIT Complexity Theorist On Leetcode](https://daily.dev/posts/mit-complexity-theorist-on-leetcode-0hduqghca) · The Developing Dev · 0 upvotes · 0 comments - [The Subset Sum Problem Solved in Linear Time for Dense Enough Inputs](https://daily.dev/posts/the-subset-sum-problem-solved-in-linear-time-for-dense-enough-inputs-sjlhgprsn) · Towards Data Science · 0 upvotes · 0 comments --- Tags: [#general-programming](https://daily.dev/tags/general-programming), [#java](https://daily.dev/tags/java), [#algorithms](https://daily.dev/tags/algorithms), [#dynamic-programming](https://daily.dev/tags/dynamic-programming) [View this post on daily.dev](https://daily.dev/posts/subsets-with-mex-in-range-ktbtrxn7n) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"Subsets with MEX in Range","url":"https://daily.dev/posts/subsets-with-mex-in-range-ktbtrxn7n","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/subsets-with-mex-in-range-ktbtrxn7n"},"datePublished":"2026-10-30T06:55:33.647Z","dateModified":"2026-10-30T06:56:01.719Z","description":"This explains an algorithm to count subsets of an array whose MEX falls within a range [l, r], returning the result modulo 10^9+7. Instead of generating all...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/1b85ac334f00e018b46697d8cb7fc2ce?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/1b85ac334f00e018b46697d8cb7fc2ce?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"C# Corner","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"C# Corner","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/ada2d584df6241748fc4e71878dc70a3","url":"https://daily.dev/sources/csharpcorner"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/subsets-with-mex-in-range-ktbtrxn7n","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"general-programming,java,algorithms,dynamic-programming","timeRequired":"PT10M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"C# Corner","item":"https://daily.dev/sources/csharpcorner"},{"@type":"ListItem","position":3,"name":"Subsets with MEX in Range"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/subsets-with-mex-in-range-ktbtrxn7n#faq","mainEntity":[{"@type":"Question","name":"How do I count subsets of an array whose MEX falls within a given range [l, r] efficiently?","acceptedAnswer":{"@type":"Answer","text":"Use frequency counting instead of generating subsets. For each candidate MEX value k, every number from 0 to k-1 must appear at least once, contributing 2^freq[x]-1 ways each; k itself must be absent (1 way); and numbers greater than k are optional, contributing 2^count ways. Multiply these together and sum over k in [l, r], computing modulo 10^9+7, for O(n+r) time. Developers tackling subset-counting problems can save similar combinatorial breakdowns on daily.dev for quick reference."}},{"@type":"Question","name":"What is the formula for counting subsets with an exact MEX value of k?","acceptedAnswer":{"@type":"Answer","text":"The count equals the product of (2^freq[x] - 1) for every value x from 0 to k-1, times 2 raised to the number of elements greater than k. Values below k must each appear at least once, the value k must be completely excluded, and values above k can be freely included or excluded, giving the combinatorial total for that exact MEX. Anyone preparing combinatorics-heavy interview problems can keep formulas like this handy via daily.dev."}},{"@type":"Question","name":"Why can't you just use 2^freq[x] instead of 2^freq[x]-1 when a value is required to be in a subset?","acceptedAnswer":{"@type":"Answer","text":"Because 2^freq[x] counts every combination of that value's occurrences including selecting none of them, which violates the requirement that the value must appear at least once. Subtracting 1 removes the all-unselected case, leaving exactly the combinations where at least one occurrence is chosen, for example 2^3-1=7 ways when there are 3 copies of a required value. Developers debugging off-by-one combinatorics errors can reference worked examples like this on daily.dev."}}]} ```