# Count and Rearrange

## Problem Statement:

Manju is given a task to find the count of a given number from the group of sorted numbers and then push the numbers to the front of the array to easily be picked up and counted.

## Discussed Solution Approaches:

- The brute force approach using loop
- The optimized approach using binary search

## The key takeaway from this coding problem:

- Learn about binary search
- Learn about swapping elements in an array

For example:If the numbers are 1, 1, 2, 2, 2, 2, 6 and you are given number 2 to count and push it to the front then, the final output would look likeOutput: 2, 2, 2, 2, 1, 1, 6

**Can you do it in the time complexity of O(logn) with the space complexity of O(1)? considering only finding and counting the numbers**

Now, for time being forget the time complexity you have been given to find out the solution, for now, think of the most basic way to find a solution to the problem.

Let’s break the problem into two subproblems:-

1. Find the count of the given number

2. Arrange the given number at the starting of all the other numbers

## Naive Solution:

The** brute-force** solution to the problem would be using **linear search**** **to count the occurrence of the number and then rearrange the number to the front of all other numbers.

Let’s look at the algorithm of this method:

start function searchElementandSwapp(array, array_size, number){

count = 0

initialIndex = 0 /* Get the count of the number and the index where it was first found */ start for (index is 0 to index is less than array_size increment index by 1)

start if(array[index] is equal to number and count = 0)

increment count by 1

set initialIndex as index

end if

start if(array[index] is equal to number and count != 0)

increment count by 1

end if

end for /* Now swapp the numbers */ start for (index is 0 to index is less than array_size and array[initialIndex] is equal to number increment by 1)

start if(array[initialIndex] is equal to number and initialIndex is less than array_size)

swapp array[index] and array[initialIndex]

increment initialIndex by 1

end if

end forend searchElementandSwapp

**This algorithm will take O(n) time to get executed and complete the operation with space of O(1)**

This algorithm will surely fail for the large size of the array and is inefficient for the larger array size, so what should we think to optimize it further?

Have you ever heard of a **binary search **algorithm?

This problem satisfies all the rules of where binary search can be used as the array is completely sorted and we could find the element in a time of** O(logn)** exactly what we want!

## Binary Search Method:

Let’s discuss the algorithm for first find the element that where it occurs in the array:

start function searchElement(array, start_index, end_index, number) start if(end_index is less than 1)

return -1

end if mid_index = start_index + (end_index - start_index) / 2

start if(array[mid_index] is equal to number)

return mid_index

end if start if(array[mid_index] is less than number)

searchElement(array, mid_index + 1, end_index, number)

end if start else

searchElement(array, start_index, mid_index - 1, number)

end elseend searchElement

Now, after searching we will need to count the occurrence of a given number in the array, for which we could write our algorithm as

start function countElement(array, array_size, number) getIndex = searchElement(array, 0, array_size - 1, number) /* if the element is not present */ start if(getIndex is equal to -1)

return 0

end if

count = 0

leftCountIndex = getIndex

rightCountIndex = getIndex

initialIndex = 0 /* this will let us know the first position where the number was found to swapp it later on */ /* count left side */

start while(leftCountIndex is greater than or equal to 0 and array[leftCountIndex] is equal to number)

increment count by 1

set initialIndex to leftCountIndex

decrement leftCountIndex by 1

end while /* count right side */ start while(rightCountIndex is less than the array_size and array[rightCountIndex] is equal to number)

increment count by 1

incrementrightCountIndex by 1

end while print count return initialIndexend countElement

Now, we have the **initialIndex** with you so we can easily use it to swap the numbers to the front **(as shown in the naive approach swapping we will use the same way)**, and boom! you have solved the problem in the desired time.

Now, since you already know the algorithm behind the problem so, you can write your own functional **code **in your desired programming language.

# Analyze:

- Time Complexity:
`O(logn)`

, where**n**is the size of the given array this is because we are using the binary search approach. - Space Complexity:
`O(1)`

, since we are not using any extra space to store the elements.

**Keep learning and keep growing and also keep exploring more!**

**All the very best!**

For more interesting and informative articles and tips follow me on **Medium**** and ****Linkedin**