Odd Occurrences In Array Algo and Implementation in Python

A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

• the elements at indexes 0 and 2 have value 9,
• the elements at indexes 1 and 3 have value 3,
• the elements at indexes 4 and 6 have value 9,
• the element at index 5 has value 7 and is unpaired.

XOR Operation :  It is a bit wise logical operation that only returns true if both the inputs are the same

Properties of XOR Here are several useful properties of XOR. This applies to plain XOR and bitwise XOR.

• x (+) 0 = x  XORing with 0 gives you back the same number. Thus, 0 is the identity for XOR. x (+) 1 = \x  XORing with 1 gives you back the negation of the bit. Again, this comes from the truth table. For bitwise XOR, the property is slightly different: 
• x ^ ~0 = ~x . That is, if you XOR with all 1's, the result will be the bitwise negation of x. 
• x (+) x = 0  XORing x with itself gives you 0. That's because x is either 0 or 1, and 0 (+) 0 = 0 and 1 (+) 1 = 0. 
• XOR is associative.That is: (x (+) y) (+) z = x (+) (y (+) z). You can verify this by using truth tables. 
• XOR is commutative.That is: x (+) y = y (+) x.

 Implementation1: Using Bit wise XOR(^)

1 2 3 4 5

def solution(A): result = 0 for number in A: result = result ^ number return result

Counter Collection : A Counter is a dict subclass for counting hashables objects. More details can be found in python documentation https://docs.python.org/3/library/collections.html#collections.Counter
 
Implementation2: Using Counter Collection
 

1 2 3 4 5

from collection import Counter def solution(A): for i in Counter(A): if Counter(A)[i]%2 == 1: return i

CyclicRotation Algo and Implementation in Python

A zero-indexed array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is also moved to the first place.

For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7]. The goal is to rotate array A K times; that is, each element of A will be shifted to the right by K indexes.

Implementation 1: Without using any inbuilt functionality

1 2 3 4 5 6

def solution(A, K): result = [] length = len(A) for i in range(length): result.insert((abs((i + K) % length)), A[i]) return result

Implementation 2: Using Deque data structure

1 2 3 4 5 6

from collections import deque def solution(A, K): items = deque(A) items.rotate(K) return list(items)

Implementation 2: One Liner solution

1 2	def solution(A, K): return A[-K % len(A):] + A[:-K % len(A)]

BinaryGap Algo and implementation in Python

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

Implementation 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

def solution(N): bin_list = [] bin_gap = 0 pre_gap = 0 flag = False while(N > 0): if N % 2 == 0: bin_list.append(0) else: bin_list.append(1) N = N // 2 for i in bin_list: if i == 1: flag = True if (bin_gap > pre_gap): pre_gap = bin_gap bin_gap = 0 elif (i == 0 and flag is True): bin_gap += 1 else: continue return pre_gap

Implementation 2:
 

1 2	def solution(N): return len(max((bin(N)[2:]).split('1' - 1), key=len))

Bubble Sort - using Python

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.


Explanation

Let us take the array of numbers "7 6 5 4 3 2 1", and sort the array from lowest number
to greatest number using bubble sort. In each step, elements written in blue  are being compared.
 six passes will be required.

First Pass: swaps- 6
(7 6 5 4 3 2 1) --> (6 7 5 4 3 2 1)
(6 7 5 4 3 2 1) --> (6 5 7 4 3 2 1)
(6 5 7 4 3 2 1) --> (6 5 4 7 3 2 1)
(6 5 4 7 3 2 1) --> (6 5 4 3 7 2 1)
(6 5 4 3 7 2 1) --> (6 5 4 3 2 7 1)
(6 5 4 3 2 7 1) --> (6 5 4 3 2 1 7)

Second Pass: swaps -5
(6 5 4 3 2 1 7) --> (5 6 4 3 2 1 7)
(5 6 4 3 2 1 7) --> (5 4 6 3 2 1 7)
(5 4 6 3 2 1 7) --> (5 4 3 6 2 1 7)
(5 4 3 6 2 1 7) --> (5 4 3 2 6 1 7)
(5 4 3 2 6 1 7) --> (5 4 3 2 1 6 7)
(5 4 3 2 1 6 7) --> (5 4 3 2 1 6 7)

Third Pass: swaps - 4
(5 4 3 2 1 6 7) --> (4 5 3 2 1 6 7)
(4 5 3 2 1 6 7) --> (4 3 5 2 1 6 7)
(4 3 5 2 1 6 7) --> (4 3 2 5 1 6 7)
(4 3 2 5 1 6 7) --> (4 3 2 1 5 6 7)
(4 3 2 1 5 6 7) --> (4 3 2 1 5 6 7)
(4 3 2 1 5 6 7) --> (4 3 2 1 5 6 7)

Forth Pass: swaps - 3
(4 3 2 1 5 6 7) --> (3 4 2 1 5 6 7)
(3 4 2 1 5 6 7) --> (3 2 4 1 5 6 7)
(3 2 4 1 5 6 7) --> (3 2 1 4 5 6 7)
 (3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)
(3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)
(3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)

fifth pass: swaps - 2
(3 2 1 4 5 6 7) --> (2 3 1 4 5 6 7)
(2 3 1 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)

sixth pass : swaps - 1
(2 1 3 4 5 6 7)--> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
------------------------

__author__ = 'kamal'def bubblesort(alist):
    for numofpass in xrange(0, len(alist)-1):
        for i in xrange(0, len(alist)-1):
            if alist[i] > alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [7, 6, 5, 4, 3, 2, 1]
bubblesort(alist)
print("----O-u-t-p-u-t-----")
print(alist)

Output--

----O-u-t-p-u-t-----
[1, 2, 3, 4, 5, 6, 7]

Insertion Sort - using Python

Talk about Algorithms and sorting comes to mind at first as it is the king of algorithms. Not only because there are many sorting algorithms but sorting is the fundamental operation in computing. Sorting means arranging items in some specific order and we see these all the times when working on our files or folder and working in database when we need records in some certain fashion. Sorting also find its use in searching and other algorithms.

There are many sorting algorithms and we will describe each algorithm and its implementation one post at a time.

Insertion sort

Insertion Sort is one of the simplest sorting algorithm. It is same as we sort  cards in our hand. We look at cards from left to right pick the unsorted card and insert it at correct position.

Explanation

For explaining the insertion sort algorithm we have taken the below unsorted list having 5 elements.

5

1

3

2

4

On first Iteration Second element will be compared with the first element it is smaller than first element they are swapped resulting in below list

1

5

3

2

4

  

On second iteration 3rd element will be checked against 1st and 2nd element and below list is formed.

1

3

5

2

4

And so on till the last element...

1

2

3

5

4

  

Final sorted list

1

2

3

4

5

Implementation

__author__ = 'Dharmjit'
def InsertionSort(list):
    for index in range(1,len(list)):
        curr = list[index]
        position = index

        while position > 0 and list[position-1] > curr:
            list[position] = list[position-1]
            position = position - 1

        list[position] = curr
    return list

l = [2,1,5,3,9,6,7]
print(InsertionSort(l))
[1,2,3,5,6,7,9]

Time complexity

Best Case Scenario:- If the list is already sorted the insertion algorithm runs in O(n) time which is linear

Worst Case Scenario:- When the List is sorted in reverse order, it will take o(n^2) time which is quadratic.