Given an Array consisting of N integers, we need to find the number of subsets of this Array of size K, where Absolute difference between the Maximum and Minimum element of the subset is at most X.
Lets say given Array is
[4 5 1 3 2] and
number of subsets satisfying given conditions will be
One of the subset is
[1 2 5] having K elements and absolute difference between minimum and maximum element
less then X i.e
This problem comes under easy-medium level.
Formally a k-combination of a set S is a subset of k distinct elements of S
- First sort the Array
[1 2 3 4 5]
Fix the first element.
Then traverse the array, counting elements whose difference with fixed element is less than or equal to X.
Calculate K-1 combinations of (counted elements - fixed element’s index), if (counted elements - fixed element’s index) is greater then
K-1because one element is fixed.
Fix the next element and repeat from step 3.
Repeat above step
For large arrays using modulo
For arrays small than 20 elemets we can find combinations directly
nCr = n! / (r! * (n-r)!)
For arrays large than 20 elements finding combinations goes out of integer limit. So we have to calculate nCr modulo M
If we have to calcuate nCr mod p(where p is a prime), we can calculate factorial mod p and then use modular inverse to find nCr mod p. If we have to find nCr mod m(where m is not prime), we can factorize m into primes and then use Chinese Remainder Theorem(CRT) to find nCr mod m.
For more info on calculating nCr for large numbers
- 13 Nov 2017 Sheet, Comparison of frontend js frameworks.
- 11 Nov 2017 Why is it so hard to develop good software?
- 04 Sep 2017 Is Graphql here to replace REST Api
- 05 Jun 2017 My awesome list of english songs
- 29 May 2017 Troll software intern
- 17 May 2017 What is icon font and why use it over png.
- 16 May 2017 Philosophical difference between ruby and python.
- 15 May 2017 Given an array, find number of subsets with k elements, where absolute difference between the maximum and mininmum element is at most x
- 15 May 2017 Automated testing of google autocomplete using cucumber and capybara
- 15 May 2017 How to manage assets in rails, difference between app, vendor and lib assets, what is asset pipeline?
- 15 May 2017 Swap elements in dom by drag and drop.
- 15 May 2017 What are the options with which protect_with_forgery is called?
- 15 May 2017 How to add csrf in ember app.
- 15 May 2017 Sessions and csrf in rails.
- 15 May 2017 Best practices while using ooor gem for making rpc calls to odoo(openerp) from ruby framework
- 09 May 2017 Integrate paytm payment with rails app
- 08 May 2017 Automated deployment on github pages using jekyll themes.
- 01 May 2017 How to add inline image in gmail.
- 01 May 2017 Undefined method `user_confirmation_path' error with devise rails.