C Tutorial

C Tutorial C Language Environment Setup Execution flow of C program C printf and Scanf C Data type C Token Variable in C Operators in C Comments in C Escape Sequence in C C – Storage Classes C Decision control statement Loop Statement in C Break, continue and goto statement in C Type Casting in C Function in C Recursion in C String in C C Array Pointer in C Dynamic memory allocation C –Structure Nested Structure in C Union in C File Handling in C C pre-processor Static Function In C Sizeof In C Selection Sort In C Scope Of Variables In C Runtime Vs Compile Time In C Random Access Lseek In C Queue Implementation In C Pseudo Code In C Prototype In C Pointer To Pointer In C Pointer Arithmetic In C Passing Array To Function In C Null Character In C Merge Sort In C Macros In C Library Functions In C Memory Leak In C Int In C Goto And Labels In C Fibonacci Series In C Fflush In C Derived Data Types In C Data Types In C Const Vs Volatile In C Character Set In C Character Class Tests In C Calloc In C C Pointers Arrays In C Include In C Clrscr In C C Vs Java String Literals In C Types Of Pointers In C Variables In C Volatile In C Why C Is A Middle Level Language Infix To Postfix Program In C Ceil function in C LCM of two numbers in C Quick sort in C Static in C function pointer as argument in C Top Array Keywords in C Add two numbers using the function in C Armstrong program in C using function Array, Declaring Arrays and Array Initialization Limitations of Inline Function in C Merge and Merge sort with example in C Do-While Loop in C For Loop in C While-Loop in C Difference between while and do-while loop in C Array Of Structures in C Data Structures And Algorithms in C Types Of Structures In C How to Avoid Structure Padding in C Use of Structure in C Do WHILE LOOP in C Programming Examples For Loop in C Programming Examples Entry Control Loop in C Exit control loop in C Infinite loop in C Nested loop in C pow() function in C String Handling functions in C Prime Number code in C Factorial Program in C using For Loop Factorial Program in C Using While Loop Fibonacci Series in C Using For Loop Fibonacci series in C using while loop Prime Number Program in C using for Loop While Loop in C programming examples Built-in functions in C Assert() Function C vs Java Strings Call Back Function in Embedded C Else If Ladder fgets() function Ftell() Function getc() function getch() function gets() function Heap Sort Nested if-else statement Pi() Function Positioning of file Write() function abs() function in C Attributes in C C program to find factorial of a number using Recursion Ferror() in c fopen() function in C Fibonacci series program in C using Recursion Formatted Input and output function in C Snake Game in C User Defined Functions in C Beep() function in C Cbrt() function in C Hook() function in C Isalnum() function in C C Program to find the Roots of a Quadratic Equation C Switch Statements Difference between rand() and srand() function in C Difference between while and for loop in C Doubly Linked list in C Example of Iteration in C How to use atoi() function in C How to use floor() function in C How to use sine() function in C How to use Typedef Struct in C Integer Promotions in C C Program Swap Numbers in cyclic order Using Call by Reference C Program to Find Largest Number Using Dynamic Memory Allocation C Program to Find the Largest Number using Ternary Operator C/C++ Program to Find the Size of int, float, double and char Find the Largest Three Distinct Elements in an Array using C/C++ Loop Questions in C Modulus on Negative Numbers in C Multiplication table program in C using For loop Nested Loops in C Programming Examples C Program for Mean and Median of an Unsorted Array Results of Comparison Operations in C and C++ Reverse a Stack using Recursion in C Simple hash() function in C strcat() Function in C Sum of N numbers in C using For loop Use of free() function in C Write a program that produces different results in C and C++ C Function Argument and Return Values Keywords in C Bank management system in C Calendar application in C Floor() Function in C Free() Function in C How to delete a file in C How to move a text in C Remove an element from an array in C Unformatted input() and output() function in C What are linker and loader in C

Find the Largest Three Distinct Elements in an Array using C/C++

In this tutorial, we will demonstrate how to use a C/C++ programme to locate the highest three different elements in an array.

C/C++ Program to Find the Largest Three Different Elements in an Array. Expected time complexity is O (n), but additional space is O (1).

Examples:

Input: array [] = {20, 18, 6, 10, 46, 75}
Output: 75, 46, 20

1st Approach:

Algorithm

  • We will create three elements called maximum1, maximum2, and maximum3 that hold the values of the three largest elements and assign their values to array [0].
  • Then, for each element, we shall loop from i -> 1 to n - 1.
  • if ( array [i] > maximum1 ) -> maximum 3 = maximum 2, maximum 2 = maximum1 , maximum1 = array [i].
  • else if ( array [i] > maximum2 ) -> maximum3 = maximum2, maximum2 = array [i].
  • else if ( array [i] > max3 ) -> maximum3 = array [i].
  • We will print all max three values at the completion of the loop.

The above algorithm is implemented as follows-

C Program:

#include <stdio.h>


void locatethethreelargestelements ( int array [], int array_size )
{
   int maximum1, maximum2, maximum3;
   maximum3 = maximum1 = maximum2 = array [0];
   for ( int i = 0; i < array_size; i++ )
   {
      if ( array[i] > maximum1 )
	  {
         maximum3 = maximum2;
         maximum2 = maximum1;
         maximum1 = array[i];
      }
      else if ( array [i] > maximum2 ) 
	  {
         maximum3 = maximum2;
         maximum2 = array [i];
      }
      else if ( array [i] > maximum3 )
         maximum3 = array [i];
   }
   printf ("\nLargest Three Different Elements in an Array are %d %d %d", maximum1 , maximum2 , maximum3 ) ;
}
int main ()
{
   int array [] = { 20, 18, 6, 10, 46, 75 };
   int n = sizeof ( array ) / sizeof ( array [0] ); 
   printf ("The array elements are : \n" );
   for (int i = 0; i < n; i++)  
      printf ("%d \t", array[i]); 
     locatethethreelargestelements (array, n);
   return 0;
} 

C++ Program:

#include <iostream>
using namespace std;


void locatethethreelargestelements ( int array [], int array_size )
{
   int maximum1, maximum2, maximum3;
   maximum3 = maximum1 = maximum2 = array [0];
   for ( int i = 0; i < array_size; i++ )
   {
      if ( array [i] > maximum1 )
	  {
         maximum3 = maximum2;
         maximum2 = maximum1;
         maximum1 = array[i];
      }
      else if ( array [i] > maximum2 ) 
	  {
         maximum3 = maximum2;
         maximum2 = array [i];
      }
      else if ( array [i] > maximum3 )
         maximum3 = array [i];
   }
   cout << endl << "\nLargest Three Different Elements in an Array are "<< maximum1 
   														 <<", "
														 << maximum2 
														 <<", "
														 << maximum3;
}
int main ()
{
   int array [] = { 20, 18, 6, 10, 46, 75 };
   int n = sizeof ( array ) / sizeof ( array [0] ); 
   cout << "The array elements are : " <<endl;
   for (int i = 0; i < n; i++)  
      cout << array[i] <<"\t"; 
     locatethethreelargestelements (array, n);
   return 0;
}

Output:

The array elements are :
20      18      6       10      46      75
Largest Three Different Elements in an Array are 75 46 20

Time Complexity: O (n)

Space Complexity: O (1)

2nd Approach:

Algorithm:

  • The array will be sorted using a sorting method.
  • Print the largest three digits.

C Program:

#include <stdio.h>
#include <stdlib.h>
 
int comparefunc ( const void* x, const void* y )
{
    return (*(int*)x - *(int*)y);
}


void findthreelargest( int array [], int no )
{
    qsort ( array, no, sizeof(int),
          comparefunc ) ;
  
printf ("Largest Three Different Elements in an Array are :");
    int checkpt = 0, cnt = 1;
    for ( int i = 1; i <= no; i++ ) 
	{
        if (cnt < 4)
		 {
            if ( checkpt != array [no - i] ) 
			{
                printf ("%d ", array [no - i]);
                checkpt = array [no - i];
                cnt++;
            }
        }
        else
            break;
    }
}
 
int main()
{
    int array[] = { 56, 78, 93, 21, 60, 100 };
    
    int no = sizeof ( array ) / sizeof ( array [0] );
    findthreelargest ( array, no );
}

C++ Program:

#include <bits/stdc++.h>
using namespace std;


void findthreelargest ( int array[], int no )
{
	cout <<"Largest Three Different Elements in an Array are: ";
	sort( array, array + no );
	int checkpt = 0, cnt = 1;
	for ( int i = 1; i <= no; i++ ) 
	{
		if ( cnt < 4 ) 
		{
			if ( checkpt != array [ no - i ] ) 
			{
				cout << array [ no - i ] << " ";
				checkpt = array [ no - i] ;
				cnt ++;
			}
		}
		else
			break;
	}
}
int main()
{
	int array[] = { 56, 78, 93, 21, 60, 100 };
	int n = sizeof ( array ) / sizeof (array [0] );
	findthreelargest ( array, n );
}

Output:

Largest Three Different Elements in an Array are: 100 93 78

Time Complexity: O (n log n)

Space Complexity: O (1)



ADVERTISEMENT
ADVERTISEMENT