We can find the smallest and second smallest element of an integers array using the c language. This question is also important and asks by the interviewer in an interview.
Let’s take an example, suppose there are an integer array iaData of 5 integers.
int iaData[5] = {3, 5, 123, 6, 1};
Here the smallest number is 1 and the second smallest number is 3.
A simple way to find the smallest and second smallest element is that sort the array in ascending order and pick its first and second elements. Its first element will be the smallest number and the second number will be the second smallest number. The time complexity of this solution is O(n log n).
// C program to find smallest and second smallest elements #include <stdio.h> #define SIZE_ARRAY(x) sizeof(x)/sizeof(x[0]); // Size of array int main() { int iaData[5] = {3,5,123,6,1}; int ArraySize = SIZE_ARRAY(iaData); int iLoop1 =0, iLoop2 =0; for(iLoop1 = 0; iLoop1 < ArraySize; iLoop1++) { for(iLoop2 = iLoop1+1; iLoop2 < ArraySize ; iLoop2++) { if(iaData[iLoop1] > iaData[iLoop2]) { iaData[iLoop1] ^= iaData[iLoop2]; iaData[iLoop2] ^= iaData[iLoop1]; iaData[iLoop1] ^= iaData[iLoop2]; } } } // Sorted array printf("\n\nSorted Array: "); for(iLoop1 = 0; iLoop1 < ArraySize; iLoop1++) printf("%d ",iaData[iLoop1]); // First element of sorted array printf("\n\nSmallest element = %d\n",iaData[0]); //Second element of sorted array printf("\n\nSecond smallest element = %d\n\n\n",iaData[1]); return 0; }
OutPut:
The above method is not better because it scans the array twice. There is also another way to find the smallest and second smallest element in a single scan of the array. The time complexity of this solution is O(n).
Here is an algorithm to find the two smallest and second smallest number in one traversal.
Algorithm to find the smallest and second smallest element:
- Creates two-variable, In this code, I have created iFirstSmallest and iSecondSmallest.
- Initialize both variables as INT_MAX
iFirstSmallest = INT_MAX
iSecondSmallest = INT_MAX - Loop through all the elements and perform the below task
1). If the current element is smaller than iFirstSmallest, then update iFirstSmallest and iSecondSmallest.
2). Else if the current element is smaller than iSecondSmallest then update iSecondSmallest.
#include <stdio.h> #include <limits.h> /* For INT_MAX */ #define SIZE_ARRAY(x) sizeof(x)/sizeof(x[0]); //Element in array void FindTwoSmallestNumber(int *piListOfData, int numbElement) { int iLoop1= 0; int iFirstSmallest = INT_MAX; int iSecondSmallest = INT_MAX; while(iLoop1 < numbElement) { if(piListOfData[iLoop1] < iFirstSmallest) { iSecondSmallest = iFirstSmallest; iFirstSmallest = piListOfData[iLoop1]; } else if((piListOfData[iLoop1] < iSecondSmallest) && (piListOfData[iLoop1] !=iFirstSmallest )) { iSecondSmallest = piListOfData[iLoop1]; } iLoop1++; } printf("First Smallest Numbers = %d\nSecond Smallest Number = %d\n ",iFirstSmallest,iSecondSmallest); } int main() { int iaData[5] = {3,5,123,6,1}; int numbElement = SIZE_ARRAY(iaData); FindTwoSmallestNumber(iaData,numbElement); return 0; }
OutPut:
Recommended Articles for you:
- How to create dynamic array in C?
- 15 Common mistakes with memory allocation.
- Arithmetic operation on pointer in C.
- How to access 2d array in C?
- A brief description of the pointer in C.
- Dangling, Void, Null and Wild Pointers
- Function pointer in c, a detailed guide
- How to use the structure of function pointer in c language?
- Memory Layout in C.
- 100 embedded C interview Questions.
- Python Interview Questions with Answer.
- File handling in C.
- Function pointer in structure.
- void pointer in C, A detail discussion.
- 100 c interview questions, your interviewer might ask.
- File handling in C.
- C format specifiers.