Sum of length of subsets which contains given value K and all elements in subsets are less than equal to K.

Objective: Given an array of numbers and integer K. Your task is to find lengths of all the subsets which contain value K and all elements in the subset are less than equal to K.

Example:

Given Input: [1, 5, 2, 3, 8, 6, 2, 4, 9, 5, 2], and K = 5
Length of subsets(all elements <= k) which contains K: 6
Explanation:
subset {1, 5, 2, 3} , length=4
subset {5, 2} , length=2
Output: 2+4 = 6

Given Input: [1, 5, 2, 3, 8, 6, 2, 4, 9, 5, 2], and K = 9
Length of subsets(all elements <= k) which contains K: 11
All elements are less than 9 so array length is our result.

Naive Approach: Use nested loops, get all the subsets with all the elements less than k and pick the ones which contain value k and add their length to answer.

Time Complexity: O(N2)

Better Approach: 

  1. Initialize currentLength = 0, answer = 0, kPresent = false.
  2. Iterate through the input array.
    1. If current element is <= k
      1. Increment currentLength by 1.
      2. If current element == k, do kPresent = true.
    2. Else
      1. Check if kPresent = true then add currentLength to answer.
      2. Reset currentLength = 0, kPresent = false
  3. Handle the edge case, if kPresent = true then add currentLength to answer.
  4. Return the answer.

Time Complexity: O(N)

Complete Code:

Output:

Given Input: [1, 5, 2, 3, 8, 6, 2, 4, 9, 5, 2], and K = 5
Length of subsets(all elements <= k) which contains K: 6

__________________________________________________
Top Companies Interview Questions..-

GoogleMicrosoftAmazonFacebookmore..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: