Java Program To Find if a given integer X appears more than N/2 times in an Array

In this tutorial, we will learn how to find if a given integer X appears more than N/2 times in a sorted array of N integers. But before moving forward, if you are not familiar with the concepts of the array, then do check the article Arrays in Java.

Input:

Array: 4 5 3 6 2 3 1 7

Search Element: 3

Output:

3 doesn't occur more than 4 times.

Program 1: To Find if a given integer X appears more than N/2 times in a sorted array of N integers.

In this approach, we will see how to find if a given integer X appears more than N/2 times in a sorted Array of N integers by using loops. The logic behind using this approach is that we count the occurrence of the element in the sorted array and then compare it with the n/2 value. One thing to keep in mind is that if we need to sort the array first before counting the occurrence of the element. This will make our task much easier as the if element which is to be searched will be in adjacent position which will make our task of counting the occurrence of that variable easier.

Algorithm

1. Start
2. Declare the array size.
3. Ask the user to initialize the array size.
4. Declare the array.
5. Ask the user to initialize the array elements.
6. Sort the array by comparing and swapping the array.
7. Print the sorted array.
8. Enter the element whose frequency you want to check.
9. Using two for loops traverse through all the elements of the array and count the frequency of the element.
10. The first for loop is used to hold the array elements.
11. The second for loop is used to check for the remaining array elements.
12. Using an if loop checks whether the element has occurred previously or not.
13. If the element has occurred previously, then increment the count variable.
14. If the element has occurred more than n/2 times, then print the message that the element has occurred more than n/2 times.
15. If the element has not occurred more than n/2 times, then print the message that the element has not occurred more than n/2 times.
16. Stop.

Below is the code for the same.

The below program demonstrates how to find if a given integer X appears more than N/2 times in a sorted array of N integers using loops.

/* Java Program to find the find if a given integer X appears more than N/2 times in a sorted Array of N integers using loops */

import java.util.*; 
  
public class Main 
{ 
    
    // Main driver method 
    public static void main(String args[]) 
    { 
  
        // Taking input from user 
        Scanner sc = new Scanner(System.in); 
        int n,x;     //Declaring Variables
        int count=0;     //declare the variable and initialize it to 0
        
        //Ask the user to enter the Array Size
        System.out.println("Enter the Array Size ");
        n=sc.nextInt();
        
        //Declare the array
        int arr[] = new int[n]; 
        System.out.println("Enter the Array elements ");
        for(int i=0;i<n;i++)   //Ask the user to initialize the array
        {
            arr[i]=sc.nextInt();
        }
        
        //Use a for loop to Sort the Array
        int temp;     //Temporary variable to hold the element
        System.out.print("Sorted Array: ");
        for(int i = 0; i < n; i++)    //Holds the array elements
        {
            for(int j = i + 1; j < n; j++)   //Checks for the remaining elements
            {
                if(arr[i] > arr[j])    //Check for the condition
                {
                    temp = arr[i];     //Sort by Swapping the variables
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        
        //Print the sorted array
        for(int i=0;i<n;i++)
        {
            System.out.print(arr[i]+" ");
        }
        System.out.println("");

         System.out.println("Enter the element which you want to check:");
        x = sc.nextInt();      //Element that you want to check
        for(int i = 0; i < n; i++)
        {
            if(arr[i] == x)
            {
                count++;      //Increment the count each time the variable is found
            }
        }

        //check whether the element has occurred for more than n/2 times 
        if(count > (n / 2))
        {
            System.out.println("Given Integer "+ x +" appears more than "+ n/2 + "times");
        }
        else
        {
            System.out.println("Given Integer "+ x +" does not appear more than "+ n/2 +" times");
        }    
        
    }   
}

Enter the Array Size 5
Enter the Array elements 6 7 5 4 3 5 6 9 6 6
Sorted Array: 3 4 5 5 6 6 6 6 7 9
Enter the element which you want to check: 6
Given Integer 6 does not appear more than 5 times