Program Asked in TCS DIGITAL














































Program Asked in TCS DIGITAL



Given an array and a number k where k is smaller than the size of the array, we need to find the K-th smallest element in the given array. It is given that all array elements are distinct.

Example :

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output: 10

METHOD 1(USING AN INBUILT FUNCTION):

def kthSmallest(arr, k): 
  
    # Sort the given array  
    arr.sort() 
  
    # Return k'th element in the  
    # sorted array  
    return arr[k-1] 

arr = [7, 10, 4, 3, 20, 15]
k = 3
print(kthSmallest(arr, k))
output : 10

METHOD 2(USING QUICK SORT):

import sys 
  
def kthSmallest(arr, l, r, k): 
  
    # If k is smaller than number of  
    # elements in array 
    if (k > 0 and k <= r - l + 1): 
      
        # Partition the array around last  
        # element and get position of pivot 
        # element in sorted array 
        pos = partition(arr, l, r) 
  
        # If position is same as k 
        if (pos - l == k - 1): 
            return arr[pos] 
        if (pos - l > k - 1): 

            return kthSmallest(arr, l, pos - 1, k) 
  
        # Else recur for right subarray 
        return kthSmallest(arr, pos + 1, r, 
                            k - pos + l - 1) 
  
    # If k is more than number of 
    # elements in array 
    return sys.maxsize 
  
 
def partition(arr, l, r): 
  
    x = arr[r] 
    i = l 
    for j in range(l, r): 
        if (arr[j] <= x): 
            arr[i], arr[j] = arr[j], arr[i] 
            i += 1
    arr[i], arr[r] = arr[r], arr[i] 
    return i 

       This Article is written by Rohit Bansal.

Comments