Skip to main content

1287. Element Appearing More Than 25% In Sorted Array

Hi, Today i bring you new Leetcode problem. Its an easy one :)

The problem is - Element Appearing More Than 25% In Sorted Array

As qs. explains itself we need to find a number that appears 25% times or more than the length of he array. So for example if array has length of 8 then the resultant number should appear 2 or more times.

The constraints given are- 1 <= arr.length <= 100, 0 <= arr[i] <= 105

So, lets look at the cases which we may encounter.

1. if length is 1. then the number itself is the result.

2. if length is divisibe by 4

3. if length is not divisible by 4.

Let's look at the code now...

 class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr)
start = 0
end = n

hm = defaultdict()

for i in arr:
hm[i] = hm.get(i, 0)+1
for i in hm:
if hm[i]>n//4:
return i

Now we will go through the code.

Step 1: Initialization

n = len(arr)
start = 0
end = n
hm = defaultdict()
  • n is the length of the input list arr.
  • start and end are initialized but not used in the provided code snippet.
  • hm is a dictionary that will be used to count the occurrences of elements in the list. It's created using defaultdict(), meaning that if a key is not found, it defaults to a count of 0.

Step 2: Counting Occurrences

for i in arr:
    hm[i] = hm.get(i, 0) + 1
  • This loop goes through each element i in the input list arr.
  • For each element i, it increments the count of i in the dictionary hm. If i is not already a key in hm, it initializes the count to 1. If i is already a key, the current count is incremented.

Step 3: FindingValue which occurs more than 25%.

for i in hm:
    if hm[i] > n // 4:
        return i
  • This loop goes through each key i in the dictionary hm.
  • For each key i, it checks if the count of i is greater than a quarter (25%) of the length of the input list (n // 4).
  • If the count of any element is greater than a quarter of the length of the input list, the method returns that elemen.

Here how this code performed.

 

Hope you like it. Happy coding

Labels:

Comments

Post a Comment

Popular posts from this blog

1235. Maximum Profit in Job Scheduling

Hi everyone, Today's post is little bit intriguing to me as it took me some time to get t the solution. I have been out of practice for a bit so I was not able to do it in the DP. I didn't want to copy the code. Though i understood the code after i checked its solution in the discussions. Anyways, i tried to do it with heap and with some thinking I was able to do it and with my surprise It performed real well. I would like to jump to the solution but first I would like to explain a little bit about heaps so you can get better understanding of the code. A heap is like a special type of list where the smallest (or largest) item is always at the front. Think of it like a priority line at a theme park, where the person with the highest priority goes to the front. There are two types of heaps: Min Heap: The smallest item is at the front. It's like standing in a line where the shortest person is always at the front. Max Heap: The largest item is at the front. It's like stand...
2 comments
Read more

Why 'C' is the default hard disk drive name

Computers have been really important part of our lives. Making our work easy and complete it in no time is the main advantage of computers. In the beginning computers were really expensive and were used by few people. Then with the increase and ease in technology computers became affordable and now-a-days everyone is using computers. Computers are proved as an evolution in our lives. Though you may be using computers but some of you may not be aware of some hidden facts. If you are using computers daily so here is one simple question for you. " Do you know why 'C' is the default hard dis drive and not 'A' or 'B'? Here is the answer : Hard disk drives became standard since 1980, Before Hard disk drives Floppy disk drivers were used as storage devices. Floppy Disk drives were initial storage devices. They came to existence in 1960's. They came in mainly 2 sizes, 5 1/4" and 3 1/2". These two floppy disk drives were labelled as Local Disk (A) and ...
Post a Comment
Read more

What is a Processor?

Smartphones have been the most important part of our lives. We have seen the evolution of our  handsets. First we saw landlines which were mess of tangled wires then we saw mobile phones which is successor of landlines. They were portable devices from which you can make calls then we witnessed emergence of Smartphones which were  considered as portable computers which also allows us to make calls. What is a Processor? Underneath that touchscreen display there is a full- fledged computer that commands your apps so that they function properly. A processor executes what you want your smartphone to do or in other word you can say processor is brain of computer. there is Exynos, Snapdragon, quad-core octa-core etc. What is a core? It is an element of surprises. They are present inside processor and are responsible for reading the command and executing them. First devices came with single core processor but later on scientists invented more advanced processors such as dual core , So...
Post a Comment
Read more