Home Author
Author

nikoo28

  • Arrays

    Separate odd and even numbers in an array.

    by nikoo28
    2 minutes read

    Question: Given an array arr[], write a function that separates even and odd numbers. The function should print first all the even numbers and then the odd numbers. Input: 4, 8, 15, 16, 23, 42 Output: 4, 8, 16, 42, 23, 15 The objective of this problem is mainly to segregate the array in two halves. One half contains all the even numbers and one half contains all the negative numbers. Naive Method:- The most naive method is to allocate a separate empty array and then we fill it as…

    0 FacebookTwitterLinkedinWhatsappEmail
  • Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 We discussed the basic 2 methods to approach this problem here:- Find majority element. (Method 1) Find majority element. (Method 2 , using sorting) It is recommended to have a look…

    0 FacebookTwitterLinkedinWhatsappEmail
  • Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 We discussed the most naive method to achieve this in our previous post. To improve the time complexity of our problem we can apply sorting technique. If we sort the array,…

    0 FacebookTwitterLinkedinWhatsappEmail
  • Arrays

    Find the majority element in an array.

    by nikoo28
    1 minutes read

    Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 The most basic method of solving this problem is to take two loops and maintain a count of each of the element. If the count reaches more than (n/2) for any…

    0 FacebookTwitterLinkedinWhatsappEmail
  • Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Count = 3 We discussed the basic method to find the number of occurrences in this post. But here, in both the cases, the time complexity is not good. We can use some of the tricks studied earlier to find a time efficient method. What we can do is:- Find the first occurrence of the element. Find…

    0 FacebookTwitterLinkedinWhatsappEmail
  • Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Count = 3 The most basic methodology to solve this problem is linear search. Just scan the array and count the number of occurrences. But this takes time O(n). We can improve the time complexity by using binary search. The steps involved in this method are:- Do a binary search and search for the data in the…

    0 FacebookTwitterLinkedinWhatsappEmail
  • Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the last occurrence of a number in O(log n) time. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Index = 4 (0 based indexing) This problem is very much similar to the binary search problem. We can apply the same methodology with just an added condition. For a number to be the last occurrence in the array, the number to the right of it must be larger. We…

    0 FacebookTwitterLinkedinWhatsappEmail
  • Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the first occurrence of a number in O(log n) time. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Index = 2 (0 based indexing) This problem is very much similar to the binary search problem. We can apply the same methodology with just an added condition. For a number to be the first occurrence in the array, the number to the left of it must be smaller. We…

    0 FacebookTwitterLinkedinWhatsappEmail
  • Question: Given a matrix that is sorted in row wise and column wise, find a number if present in the most efficient way. Input: Find if 54 is present in matrix. 4 8 15 16 23 6 9 20 21 44 8 11 24 26 49 9 13 25 27 54 10 17 29 30 66 Output: Present Method 1(Brute force):- Here, we use two loops search the element in entire matrix. Its a linear search so its not an efficient way to solve this problem. Time Complexity:- O(rows *…

    0 FacebookTwitterLinkedinWhatsappEmail

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More