Check If a Number Is Majority Element in a Sorted Array

🏠 ⬅️ ➡️

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element, or false otherwise.

A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.

Example 1:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5 Output: true Explanation: The value 5 appears 5 times and the length of the array is 9. Thus, 5 is a majority element because 5 > 9/2 is true.

Example 2:

Input: nums = [10,100,101,101], target = 101 Output: false Explanation: The value 101 appears 2 times and the length of the array is 4. Thus, 101 is not a majority element because 2 > 4/2 is false.

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i], target <= 109
  • nums is sorted in non-decreasing order.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 9
    integer, dimension(n) :: nums
    integer :: i, target
    logical :: result

    ! Example 1
    nums = [2, 4, 5, 5, 5, 5, 5, 6, 6]
    target = 5
    result = majorityElement(nums, target)
    write (unit=*, fmt='(L1)') result

    ! Example 2
    nums = [10, 100, 101, 101]
    target = 101
    result = majorityElement(nums, target)
    write (unit=*, fmt='(L1)') result

contains

    function majorityElement(nums, target) result(result_)
        implicit none

        integer, dimension(:), intent(in) :: nums
        integer, intent(in) :: target
        logical :: result_

        integer :: count

        count = 0
        do i = 1, size(nums)
            if (nums(i) == target) then
                count = count + 1
            end if
        end do

        result_ = count > size(nums) / 2
    end function majorityElement
end program main
❌ Compiled
❌ Executed
❌ Correct 
module majority_element
    implicit none

contains

    function is_majority_element(nums, target) result(is_majority)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: target
        logical :: is_majority

        ! Local variables
        integer :: i, count

        ! Initialize variables
        is_majority = .false.
        count = 0

        ! Loop through the array and count the number of occurrences of the target element
        do i = 1, size(nums)
            if (nums(i) == target) then
                count = count + 1
            end if
        end do

        ! Check if the target element is a majority element
        if (count > size(nums) / 2) then
            is_majority = .true.
        end if

    end function is_majority_element

end module majority_element

program main
    use majority_element
    implicit none

    ! Test cases
    integer, parameter :: nums1(8) = [2, 4, 5, 5, 5, 5, 5, 6]
    integer, parameter :: target1 = 5
    integer, parameter :: nums2(4) = [10, 100, 101, 101]
    integer, parameter :: target2 = 101
    integer, parameter :: nums3(10) = [3, 3, 4, 5, 5, 5, 5, 6, 6]
    integer, parameter :: target3 = 5

    ! Output
    logical :: is_majority

    ! Test case 1
    is_majority = is_majority_element(nums1, target1)
    if (is_majority) then
        write (*,*) "Test case 1: Pass"
    else
        write (*,*) "Test case 1: Fail"
    end if

    ! Test case 2
    is_majority = is_majority_element(nums2, target2)
    if (.not. is_majority) then
        write (*,*) "Test case 2: Pass"
    else
        write (*,*) "Test case 2: Fail"
    end if

    ! Test case 3
    is_majority = is_majority_element(nums3, target3)
    if (is_majority) then
        write (*,*) "Test case 3: Pass"
    else
        write (*,*) "Test case 3: Fail"
    end if

end program main
🌐 Data from online sources 
def is_majority_element(nums, target):
    count = 0
    for num in nums:
        if num == target: count += 1
        if count > len(nums) / 2: return True
    return False

The algorithm is simple, we iterate through the array, and when we find the target number, we increment the count variable. If the count variable ever becomes greater than nums.length / 2, we return true because the target is a majority element. Otherwise, after iterating through the array, we return false because the target is not a majority element. This approach has a linear time complexity of O(n), where n is the length of the array.

🌐 Data from online sources 
bool isMajorityElement(vector<int>& nums, int target) {
    int count = 0;
    for (int num : nums) {
        if (num == target) count++;
        if (count > nums.size() / 2) return true;
    }
    return false;
}

The algorithm is simple, we iterate through the array, and when we find the target number, we increment the count variable. If the count variable ever becomes greater than nums.length / 2, we return true because the target is a majority element. Otherwise, after iterating through the array, we return false because the target is not a majority element. This approach has a linear time complexity of O(n), where n is the length of the array.