C Exercises: Find minimum number of swaps required to gather all elements less than or equals to k

Last update on March 18 2025 13:20:50 (UTC/GMT +8 hours)

105. Minimum Swaps to Group Elements ≤ k

Write a program in C to find the minimum number of swaps required to gather all elements less than or equal to k.

Expected Output:
The given array is:
2 7 9 5 8 7 4
The minimum swap required is: 2

The task is to write a C program that calculates the minimum number of swaps required to gather all elements in an array that are less than or equal to a given value k. The program should iterate through the array, count the elements that meet the condition, and determine the minimal number of swaps needed to group these elements together. Finally, it should display the minimum number of swaps required.

Sample Solution:

C Code:

#include<stdio.h>

// Function to find the minimum number of swaps required to bring elements less than or equal to 'k' together
int minSwap(int *arr1, int n, int k) 
{ 
    int ctr = 0; 

    // Count elements less than or equal to 'k' in the array
    for (int i = 0; i < n; ++i) 
        if (arr1[i] <= k) 
            ++ctr; 

    int gelem = 0; 

    // Count elements greater than 'k' within the first 'ctr' elements
    for (int i = 0; i < ctr; ++i) 
        if (arr1[i] > k) 
            ++gelem; 

    int noswp = gelem; 

    // Move the window of size 'ctr' through the array and count the number of elements greater than 'k' to minimize swaps
    for (int i = 0, j = ctr; j < n; ++i, ++j) 
	{ 
        if (arr1[i] > k)
        {
            --gelem; 
        }
        if (arr1[j] > k)
        {
            ++gelem; 
        }
    }

    // Update the minimum swaps required
    if(noswp > gelem)
    {
        noswp = gelem;
    }
    if(noswp < gelem)
    {
        noswp = noswp;
    }            
    return noswp; 
} 

// Main function
int main() 
{ 
    int arr1[] = {2, 7, 9, 5, 8, 7, 4}; // Given array
    int n = sizeof(arr1) / sizeof(arr1[0]); // Calculate array size
    int k = 7; // Given 'k' value for comparison
    int i = 0; 

    // Display the given array
    printf("The given array is:  \n");
    for(i = 0; i < n; i++)
    {
        printf("%d  ", arr1[i]);
    }
    printf("\n");

    // Calculate and display the minimum swaps required to bring elements less than or equal to 'k' together
    printf("The minimum swap required is: %d", minSwap(arr1, n, k)); 
    return 0; 
}

Output:

The given array is:  
2  7  9  5  8  7  4  
The minimum swap required is: 2  

Visual Presentation:

Flowchart 1:

Flowchart 2:

For more Practice: Solve these Related Problems:

• Write a C program to compute the minimum number of swaps required to group all elements less than or equal to k together using sliding window.
• Write a C program to count swaps needed by first counting “bad” elements and then sliding a window.
• Write a C program to determine the minimum swaps using dynamic programming for grouping elements ≤ k.
• Write a C program to find the minimum number of adjacent swaps required to bring all qualifying elements together.

C Programming Code Editor:

Click to Open Editor

Previous: Write a program in C to rearrange an array such that even index elements are smaller and odd index elements are greater than their next.
Next: Write a program in C to convert the array in such a way that double its value and replace the next number with 0 if current and next element are same and rearrange the array such that all 0's shifted to the end.