Blogs Hub

by Sumit Chourasia | Jun 10, 2020 | Category :coding | Tags : arrayआसानc-sharpडेटा-संरचनाleetcodealgorithm

Element Appearing More Than 25% In Sorted Array - Easy - LeetCode - मिनी टीवी

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]

Output: 6

Constraints:

1 <= arr.length <= 10^4

0 <= arr[i] <= 10^5

Solution:

``````using System;
using System.Collections.Generic;
using System.Text;

{
public class FindSpecialIntegerSoln
{
public int FindSpecialInteger(int[] arr)
{
var map = new Dictionary<int, int>();

for (int i = 0; i < arr.Length; i++)
{
if (map.ContainsKey(arr[i]))
{
map[arr[i]]++;
}
else
{
}
}

// As it is mentioned that there will be at least one number
// that will be having more than 25% frequency count.
int max = 0;
int value = 0;
foreach (var item in map)
{
if (max < item.Value)
{
max = item.Value;
value = item.Key;
}
}

return value;
}
}
}
``````

Time Complexity: O(n)

Space Complexity: O(n)

Unit Tests:

``````using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.Array
{
[TestClass]
public class FindSpecialIntegerSolnTests
{
[TestMethod]
public void FindSpecialIntegerSoln_First()
{
var arr = new int[] { 1, 2, 2, 6, 6, 6, 6, 7, 10 };
var output = 6;
var res = new FindSpecialIntegerSoln().FindSpecialInteger(arr);

Assert.AreEqual(res, output);
}
}
}
``````

Contributed By: Sumit Chourasia
Contributed By: Sumit Chourasia
Contributed By: Sumit Chourasia
Contributed By: Sumit Chourasia