## Number of swaps to sort when only adjacent swapping allowed

Given an array arr[] of non negative integers. We can perform a swap operation on any two adjacent elements in the array. Find the minimum number of swaps needed to sort the array in ascending order.

Examples:

```Input  : arr[] = {3, 2, 1}
Output : 3
We need to do following swaps
(3, 2), (3, 1) and (1, 2)

Input  : arr[] = {1, 20, 6, 4, 5}
Output : 5
```
)

There is an interesting solution to this problem. It can be solved using the fact that number of swaps needed is equal to number of inversions. So we basically need to count inversions in array.

The fact can be established using below observations:
1) A sorted array has no inversions.
2) An adjacent swap can reduce one inversion. Doing x adjacent swaps can reduce x inversions in an array.

`// C++ program to count number of swaps required`
`// to sort an array when only swapping of adjacent`
`// elements is allowed.`
`#include <bits/stdc++.h>`
`/* This function merges two sorted arrays and returns inversion`
`   ``count in the arrays.*/`
`int` `merge(``int` `arr[], ``int` `temp[], ``int` `left, ``int` `mid, ``int` `right)`
`{`
`    ``int` `inv_count = 0;`
`    ``int` `i = left; ``/* i is index for left subarray*/`
`    ``int` `j = mid;  ``/* i is index for right subarray*/`
`    ``int` `k = left; ``/* i is index for resultant merged subarray*/`
`    ``while` `((i <= mid - 1) && (j <= right))`
`    ``{`
`        ``if` `(arr[i] <= arr[j])`
`            ``temp[k++] = arr[i++];`
`        ``else`
`        ``{`
`            ``temp[k++] = arr[j++];`
`            ``/* this is tricky -- see above explanation/`
`              ``diagram for merge()*/`
`            ``inv_count = inv_count + (mid - i);`
`        ``}`
`    ``}`
`    ``/* Copy the remaining elements of left subarray`
`     ``(if there are any) to temp*/`
`    ``while` `(i <= mid - 1)`
`        ``temp[k++] = arr[i++];`
`    ``/* Copy the remaining elements of right subarray`
`     ``(if there are any) to temp*/`
`    ``while` `(j <= right)`
`        ``temp[k++] = arr[j++];`
`    ``/*Copy back the merged elements to original array*/`
`    ``for` `(i=left; i <= right; i++)`
`        ``arr[i] = temp[i];`
`    ``return` `inv_count;`
`}`
`/* An auxiliary recursive function that sorts the input`
`   ``array and returns the number of inversions in the`
`   ``array. */`
`int` `_mergeSort(``int` `arr[], ``int` `temp[], ``int` `left, ``int` `right)`
`{`
`    ``int` `mid, inv_count = 0;`
`    ``if` `(right > left)`
`    ``{`
`        ``/* Divide the array into two parts and call`
`          ``_mergeSortAndCountInv() for each of the parts */`
`        ``mid = (right + left)/2;`
`        ``/* Inversion count will be sum of inversions in`
`           ``left-part, right-part and number of inversions`
`           ``in merging */`
`        ``inv_count  = _mergeSort(arr, temp, left, mid);`
`        ``inv_count += _mergeSort(arr, temp, mid+1, right);`
`        ``/*Merge the two parts*/`
`        ``inv_count += merge(arr, temp, left, mid+1, right);`
`    ``}`
`    ``return` `inv_count;`
`}`
`/* This function sorts the input array and returns the`
`   ``number of inversions in the array */`
`int` `countSwaps(``int` `arr[], ``int` `n)`
`{`
`    ``int` `temp[n];`
`    ``return` `_mergeSort(arr, temp, 0, n - 1);`
`}`
`/* Driver progra to test above functions */`
`int` `main(``int` `argv, ``char``** args)`
`{`
`    ``int` `arr[] = {1, 20, 6, 4, 5};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``printf``(``"Number of swaps is %d \n"``, countSwaps(arr, n));`
`    ``return` `0;`
`}`

Output:

```Number of swaps is 5
```

Time Complexity : O(n Log n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Minimum number of swaps required to sort an array

Given an array of n distinct elements, find the minimum number of swaps required to sort the array.

Examples:

```Input : {4, 3, 2, 1}
Output : 2
Explanation : Swap index 0 with 3 and 1 with 2 to
form the sorted array {1, 2, 3, 4}.

Input : {1, 5, 4, 3, 2}
Output : 2
```

This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i’th index must be present at j’th index in the sorted array.

```
Graph for {4, 3, 2, 1}
```

The graph will now contain many non-intersecting cycles. Now a cycle with 2 nodes will only require 1 swap to reach the correct ordering, similarly a cycle with 3 nodes will only require 2 swap to do so.

```
Graph for {4, 5, 2, 1, 5}
```

Hence,

• ans = Σi = 1k(cycle_size – 1)

where k is the number of cycles

Below is the C++ implementation of the idea.

`// C++ program to find  minimum number of swaps`
`// required to sort an array`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// Function returns the minimum number of swaps`
`// required to sort the array`
`int` `minSwaps(``int` `arr[], ``int` `n)`
`{`
`    ``// Create an array of pairs where first`
`    ``// element is array element and second element`
`    ``// is position of first element`
`    ``pair<``int``, ``int``> arrPos[n];`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``arrPos[i].first = arr[i];`
`        ``arrPos[i].second = i;`
`    ``}`
`    ``// Sort the array by array element values to`
`    ``// get right position of every element as second`
`    ``// element of pair.`
`    ``sort(arrPos, arrPos + n);`
`    ``// To keep track of visited elements. Initialize`
`    ``// all elements as not visited or false.`
`    ``vector<``bool``> vis(n, ``false``);`
`    ``// Initialize result`
`    ``int` `ans = 0;`
`    ``// Traverse array elements`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``// already swapped and corrected or`
`        ``// already present at correct pos`
`        ``if` `(vis[i] || arrPos[i].second == i)`
`            ``continue``;`
`        ``// find out the number of  node in`
`        ``// this cycle and add in ans`
`        ``int` `cycle_size = 0;`
`        ``int` `j = i;`
`        ``while` `(!vis[j])`
`        ``{`
`            ``vis[j] = 1;`
`            ``// move to next node`
`            ``j = arrPos[j].second;`
`            ``cycle_size++;`
`        ``}`
`        ``// Update answer by adding current cycle.`
`        ``ans += (cycle_size - 1);`
`    ``}`
`    ``// Return result`
`    ``return` `ans;`
`}`
`// Driver program to test the above function`
`int` `main()`
`{`
`    ``int` `arr[] = {1, 5, 4, 3, 2};`
`    ``int` `n = (``sizeof``(arr) / ``sizeof``(``int``));`
`    ``cout << minSwaps(arr, n);`
`    ``return` `0;`
`}`

Output:

```2
```

Time Complexity: O(n*log(n))
Auxiliary Space: O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Subarray Inversions

We have an array A of n integers that we’re planning on sorting. Specifically, we want to know how close the array is to sorted. In order to achieve this, we introduce the idea of an inversion. An inversion in array is a pair of two indices i and jsuch that i < j and A[i] > A[j]. If our array contains one inversion, we need only swap A[i]and A[j] in order to sort the array. An array that contains 0 inversions is by definition sorted.

Problem: Given an array A of n integers, find the sum of the number of inversions in all subarrays of length k. To clarify, one must determine the number of inversions in each of the n – k + 1 subarrays of length k and add them together.

Input: The first line contains two space separated integers n and k. The next line contains a sequence of n space separated integers where the ith integer in the sequence is A[i].

Examples:

```Input : arr[] = {1 2 3 4 5 6}
k = 2
Output : 0

Input : arr[] = {1 6 7 2}
k = 3
Output : 2
There are two subarrays of size 3,
{1, 6, 7} and {6, 7, 2}. Count of
inversions in first subarray is 0
and count of inversions in second
subarray is 2. So sum is 0 + 2 = 2

Input :  8 4
12 3 14 8 15 1 4 22
Output : 14

Input :  10 5
15 51 44 44 76 50 29 88 48 50
Output : 25
```

[1] Naive Approach

This problem seems fairly trivial at first, and we can easily implement a naive algorithm to brute force the solution. We simply create a window of length k and roll the window along A, adding the number of inversions in the window at each iteration. To find the number of inversions, the simplest approach is to use two for loops to consider all pairs of elements and increment a counter if the pair forms an inversion.

This approach is very easy to implement, but is it efficient? Let’s analyze the algorithm. The outermost loop runs n – k + 1 times, once for each k-subarray of A. At each of these iterations, we find the number of inversions in the window. To do this, we consider element 1 and elements 2, …, n, then element 2 and elements 3, …, n until element n – 1 and element n. Effectively, we’re performing n + (n – 1) + (n – 2) + … + 1 = n(n + 1)/2operations. Thus, our algorithm performs approximately (n – k + 1)(n)(n + 1)/2operations which is O(n^3 – kn^2). Since k can range from 1 to n, the worst case performance for this algorithm is O(n^3) when k = n/2. We can do better!

`public` `class` `Subarray_Inversions {`
`    ``// Inversion counting method, slides window of [start,`
`    ``// end] across array`
`    ``static` `int` `inversion_count(``int` `n, ``int` `k, ``int``[] a)`
`    ``{`
`        ``int` `count = ``0``;`
`        ``for` `(``int` `start = ``0``; start < n - k + ``1``; start++) {`
`            ``int` `end = start + k;`
`            ``count += bubble_count(a, start, end);`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// Helper function, counts number of inversions via `
`    ``// bubble sort loop`
`    ``public` `static` `int` `bubble_count(``int``[] arr, ``int` `start, ``int` `end)`
`    ``{`
`        ``int` `count = ``0``;`
`        ``for` `(``int` `i = start; i < end; i++) {`
`            ``for` `(``int` `j = i + ``1``; j < end; j++) {`
`                ``if` `(arr[i] > arr[j]) {`
`                    ``count++;`
`                ``}`
`            ``}`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``public` `static` `void` `main(String[] args)`
`    ``{`
`        ``int` `n = ``10``;`
`        ``int``[] arr = { ``15``, ``51``, ``44``, ``44``, ``76``, ``50``, ``29``, ``88``, ``48``, ``50` `};`
`        ``int` `k = ``5``;`
`        ``long` `result = inversion_count(n, k, arr);`
`        ``System.out.println(result);`
`    ``}`
`}`

Output:

``` 25
```

[2] Mergesort-based Implementation

One optimization we can make is improving our inefficient, quadratic-time inversion counting method. One approach could involve using a mergesort-based method as outlined in this article. Since this runs in O(nlogn), our overall runtime is reduced to O(n^2logn), which is better, but still won’t be able to handle cases for which n = 10^6 for instance.

`import` `java.util.*;`
`public` `class` `Subarray_Inversions {`
`    ``// Inversion counting method, slides window of [start,`
`    ``// end] across array`
`    ``static` `int` `inversion_count(``int` `n, ``int` `k, ``int``[] a)`
`    ``{`
`        ``int` `count = ``0``;`
`        ``for` `(``int` `start = ``0``; start < n - k + ``1``; start++) {`
`            ``int``[] sub_array = ``new` `int``[k];`
`            ``for` `(``int` `i = start; i < start + k; i++) {`
`                ``sub_array[i - start] = a[i];`
`            ``}`
`            ``count += subarray_inversion_count(sub_array);`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// Counts number of inversions when merging`
`    ``public` `static` `long` `merge_inversion_count(``int``[] arr,`
`                                ``int``[] left, ``int``[] right)`
`    ``{`
`        ``int` `i = ``0``, j = ``0``, count = ``0``;`
`        ``while` `(i < left.length || j < right.length) {`
`            ``if` `(i == left.length) {`
`                ``arr[i + j] = right[j];`
`                ``j++;`
`            ``} ``else` `if` `(j == right.length) {`
`                ``arr[i + j] = left[i];`
`                ``i++;`
`            ``} ``else` `if` `(left[i] <= right[j]) {`
`                ``arr[i + j] = left[i];`
`                ``i++;`
`            ``} ``else` `{`
`                ``arr[i + j] = right[j];`
`                ``count += left.length - i;`
`                ``j++;`
`            ``}`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// Divide and conquer approach -- splits array and counts `
`    ``// inversions via merge method`
`    ``public` `static` `long` `subarray_inversion_count(``int``[] arr)`
`    ``{`
`        ``if` `(arr.length < ``2``)`
`            ``return` `0``;`
`        ``int` `m = (arr.length + ``1``) / ``2``;`
`        ``int` `left[] = Arrays.copyOfRange(arr, ``0``, m);`
`        ``int` `right[] = Arrays.copyOfRange(arr, m, arr.length);`
`        ``return` `subarray_inversion_count(left) + `
`               ``subarray_inversion_count(right) + `
`               ``merge_inversion_count(arr, left, right);`
`    ``}`
`    ``public` `static` `void` `main(String[] args)`
`    ``{`
`        ``int` `n = ``10``;`
`        ``int``[] arr = { ``15``, ``51``, ``44``, ``44``, ``76``, ``50``, ``29``, ``88``, ``48``, ``50` `};`
`        ``int` `k = ``5``;`
`        ``long` `result = inversion_count(n, k, arr);`
`        ``System.out.println(result);`
`    ``}`
`}`

Output:

``` 25
```

[3] Overlapping Subarrays Implementation

Let’s revisit our overall approach. We’re looking at the window [0, k) and finding the number of inversions, then we look at [1, k+1). There’s a significant overlap in this range: we’ve already counted the number of inversions in [1, k) during the first iteration, and now we’re counting them again! Instead of counting inversions, let’s count the change in inversions from one window to the next. Effectively, shifting the window is just adding one element to the head of the window and removing an element from its tail — the body of the window remains the same. Checking for inversions among internal elements would be redundant; all we need to do is add the number of inversions induced by the new element and subtract the number of inversions induced by the removed element. We now only need to count the number of inversions in the first window, which we can do in O(klogk) time, and for each of the n – k additional windows, we simply perform one iteration through the k elements in the array to find the change in the number of inversions. Our overall runtime is now O(k(n – k) + klogk) = O(nk – k)which is still worst case O(n^2).

`import` `java.util.*;`
`public` `class` `Subarray_Inversions {`
`    ``// Inversion counting method, slides window of [start,`
`    ``// end] across array`
`    ``static` `long` `inversion_count(``int` `n, ``int` `m, ``int``[] arr)`
`    ``{`
`        ``long` `count = ``0``;`
`        ``count += subarray_inversion_count_initial(Arrays.copyOfRange(arr, ``0``, m));`
`        ``long` `subarray_count = subarray_inversion_count_initial(Arrays.copyOfRange(arr, ``1``, m));`
`        ``for` `(``int` `start = ``1``; start <= n - m; start++) {`
`            ``int` `end = start + m - ``1``;`
`            ``long``[] ans = subarray_inversion_count(arr, start, end, subarray_count);`
`            ``count += ans[``0``];`
`            ``subarray_count = ans[``1``];`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// start >=1; find inversion in interval [start, end)`
`    ``public` `static` `long``[] subarray_inversion_count(``int``[] arr, ``int` `start,`
`                                          ``int` `end, ``long` `subarray_count)`
`    ``{`
`        ``int` `new_element = arr[end];`
`        ``long` `count = subarray_count;`
`        ``for` `(``int` `i = start; i < end; i++) {`
`            ``if` `(new_element < arr[i])`
`                ``count++;`
`        ``}`
`        ``long` `totalSum = count;`
`        ``int` `last_element = arr[start];`
`        ``for` `(``int` `i = start + ``1``; i <= end; i++) {`
`            ``if` `(last_element > arr[i])`
`                ``count--;`
`        ``}`
`        ``long``[] ans = { totalSum, count };`
`        ``return` `ans;`
`    ``}`
`    ``// Counts number of inversions when merging`
`    ``public` `static` `long` `merge_inversion_count(``int``[] arr, ``int``[] left, `
`                                                       ``int``[] right)`
`    ``{`
`        ``int` `i = ``0``, j = ``0``, count = ``0``;`
`        ``while` `(i < left.length || j < right.length) {`
`            ``if` `(i == left.length) {`
`                ``arr[i + j] = right[j];`
`                ``j++;`
`            ``} ``else` `if` `(j == right.length) {`
`                ``arr[i + j] = left[i];`
`                ``i++;`
`            ``} ``else` `if` `(left[i] <= right[j]) {`
`                ``arr[i + j] = left[i];`
`                ``i++;`
`            ``} ``else` `{`
`                ``arr[i + j] = right[j];`
`                ``count += left.length - i;`
`                ``j++;`
`            ``}`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// Divide and conquer approach -- splits array and counts`
`    ``// inversions via merge method`
`    ``public` `static` `long` `subarray_inversion_count_initial(``int``[] arr)`
`    ``{`
`        ``if` `(arr.length < ``2``)`
`            ``return` `0``;`
`        ``int` `m = (arr.length + ``1``) / ``2``;`
`        ``int` `left[] = Arrays.copyOfRange(arr, ``0``, m);`
`        ``int` `right[] = Arrays.copyOfRange(arr, m, arr.length);`
`        ``return` `subarray_inversion_count_initial(left) + `
`               ``subarray_inversion_count_initial(right) + `
`               ``merge_inversion_count(arr, left, right);`
`    ``}`
`    ``public` `static` `void` `main(String[] args) ``throws` `Exception`
`    ``{`
`        ``int` `n = ``10``;`
`        ``int``[] arr = { ``15``, ``51``, ``44``, ``44``, ``76``, ``50``, ``29``, ``88``, ``48``, ``50` `};`
`        ``int` `k = ``5``;`
`        ``long` `result = inversion_count(n, k, arr);`
`        ``System.out.println(result);`
`    ``}`
`}`

Output:

``` 25
```

[4] Binary Indexed Tree Implementation

Iterating over each window seems inevitable, so the bottleneck here appears to be the way we handle the windows. We know that consecutive windows overlap significantly, so all we need to know is the number of elements greater than the newly added element and number of elements less than the newly removed element. Many times, algorithms that perform the same or similar operation(s) repeatedly can be improved by the use of a more robust data structure. In our case, we’re looking for a dynamic data structure that can efficiently answer queries about an element’s relative position when sorted. We can use a self-balancing binary tree to actually maintain a sorted list, but insertion/removal takes logarithmic time. We can do this in constant time using a Binary Indexed Tree, or Fenwick Tree.

A binary indexed tree is a tree represented in the form of an array. It uses clever bit manipulation to compute the cumulative sum of elements very efficiently. We can call the function update(index, val) function to add val to BIT[index] and all of the ancestors of index. The function read(index) returns the sum of the values stored at BIT[index]and all of the ancestors of index in the tree. Thus, calling read(index) returns the cumulative sum of all elements in BIT less than or equal to index. Instead of storing values, if we simply store 1, we can use read(index + 1) to determine the number of elements less than index. Now, we can construct a binary indexed tree by inserting the elements (updating) of the first window. For subsequent windows, we can remove the trailing element by calling update(tail_element, -1) and add the new element with update(head_element, 1). Since this is a tree, the longest possible root-node path is O(logk), Thus, we achieve an optimal runtime of O(nlogk + klogk) = O(nlogk)!

Or do we…? Remember, binary indexed trees allocate memory for every possible value in the range [0, max_element], so this requires O(max_element) time and space. For very sparse arrays, this can be quite costly. Instead, we can define a hash function to . We can do this because we’re only concerned about inversions — as long as we keep the relative magnitude the same (i.e. A[i] <= A ==> A[hash(i)] <= A[hash(j)]), our solution will still be correct. Thus, we can map all the elements in A to the set {0, 1, 2, …, n}, yielding a guaranteed runtime of O(nlogk).

`import` `java.util.*;`
`public` `class` `Subarray_Inversions {`
`    ``// Declare binary indexed tree with global scope`
`    ``static` `BIT bit;`
`    ``// first window, counts first k elements and creates`
`    ``// BIT`
`    ``static` `long` `inversionCountBIT1(``int``[] arr, ``int` `start, `
`                                               ``int` `end)`
`    ``{`
`        ``bit = ``new` `BIT(arr.length);`
`        ``long` `count = ``0``;`
`        ``for` `(``int` `index = start; index >= end; index--) {`
`            ``count += bit.read(arr[index]);`
`            ``bit.update(arr[index], ``1``);`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``// subsequent windows, removes previous element, adds`
`    ``// new element, and increments change in inversions`
`    ``static` `long` `inversionCountBIT2(``int``[] arr, ``int` `start,`
`                                       ``int` `end, ``long` `val)`
`    ``{`
`        ``bit.update(arr[start + ``1``], -``1``); ``// remove trailing element`
`        ``// find number of elements in range [start, end-1] `
`        ``// greater than first`
`        ``int` `numGreaterThanFirst = start - end - bit.read(arr[start + ``1``] + ``1``);`
`        ``long` `count = val + bit.read(arr[end]) - numGreaterThanFirst;`
`        ``bit.update(arr[end], ``1``); ``// adds leading element`
`        ``return` `count;`
`    ``}`
`    ``// Main method to count inversions in size k subarrays`
`    ``public` `static` `long` `inversionCount(``int` `n, ``int` `k, ``int``[] arr)`
`    ``{`
`        ``bit = ``new` `BIT(n);`
`        ``HashMap<Integer, Integer> freq = ``new` `HashMap<Integer, Integer>();`
`        ``int``[] asort = arr.clone();`
`        ``// Map elements from [A[0]...A[n-1]] to [1...n]`
`        ``Arrays.sort(asort);`
`        ``int` `index = ``0``;`
`        ``int` `current = ``1``;`
`        ``for` `(``int` `i = ``0``; i < n; i++) {`
`            ``if` `(!freq.containsKey(asort[i])) {`
`                ``freq.put(asort[i], current);`
`                ``current++;`
`            ``}`
`        ``}`
`        ``for` `(``int` `i = ``0``; i < n; i++) {`
`            ``arr[i] = freq.get(arr[i]);`
`        ``}`
`        ``long` `count = ``0``;`
`        ``long` `val = ``0``;`
`        ``//[start - end] ==> start - end = k+1`
`        ``for` `(``int` `start = n - ``1``; start >= k - ``1``; start--) {`
`            ``int` `end = start - k + ``1``;`
`            ``if` `(start == n - ``1``) { ``// First pass`
`                ``val = inversionCountBIT1(arr, n - ``1``, n - k);`
`            ``} ``else` `{ ``// subsequent passes`
`                ``val = inversionCountBIT2(arr, start, end, val);`
`            ``}`
`            ``count += val;`
`        ``}`
`        ``return` `count;`
`    ``}`
`    ``public` `static` `void` `main(String[] args) ``throws` `Exception`
`    ``{`
`        ``int` `n = ``10``;`
`        ``int``[] arr = { ``15``, ``51``, ``44``, ``44``, ``76``, ``50``, ``29``, ``88``, ``48``, ``50` `};`
`        ``int` `k = ``5``;`
`        ``long` `result = inversionCount(n, k, arr);`
`        ``System.out.println(result);`
`    ``}`
`    ``// Implementation of Binary Indexed Tree`
`    ``static` `class` `BIT {`
`        ``int``[] tree;`
`        ``int` `maxVal;`
`    ``public` `BIT(``int` `N)`
`        ``{`
`            ``tree = ``new` `int``[N + ``1``];`
`            ``maxVal = N;`
`        ``}`
`        ``// Updates BIT, starting with element at index `
`        ``// and all ancestors`
`        ``void` `update(``int` `index, ``int` `val)`
`        ``{`
`            ``while` `(index <= maxVal) {`
`                ``tree[index] += val;`
`                ``index += (index & -index);`
`            ``}`
`        ``}`
`        ``// Returns the cumulative frequency of index `
`        ``// starting with element at index and all ancestors`
`        ``int` `read(``int` `index)`
`        ``{`
`            ``--index;`
`            ``int` `cumulative_sum = ``0``;`
`            ``while` `(index > ``0``) {`
`                ``cumulative_sum += tree[index];`
`                ``index -= (index & -index);`
`            ``}`
`            ``return` `cumulative_sum;`
`        ``}`
`    ``};`
`}`

Output:

``` 25

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Counting inversions in all subarrays of given size

Given an array and an integer k, count all inversions in all subarrays of size k.

Example:

```Input : a[] = {7, 3, 2, 4, 1},
k = 3;
Output : 6
Explanation: subarrays of size 3 are -
{7, 3, 2}
{3, 2, 4}
{2, 4, 1}
and there inversion count are 3, 1, 2
respectively. So, total number of
inversions are  6.```

It is strongly recommended to refer Inversion count in an array using BIT

The process of counting inversion is same as in the above linked article. First, we calculate the inversion in first k (k is given size of subarray) elements in the array using BIT. Now after this for every next subarray we subtract the inversion of first element of previous subarray and add the inversions of the next element not included in the previous subarray. This process is repeated until the last subarray is processed.On the above example this algorithm works like this-

```a[] = {7, 3, 2, 4, 1},
k = 3;

Inversion are counted for first subarray
A = {7, 3, 2} Let this be equal to invcount_A.

For counting the inversion of subarray B we
subtract the inversion of first element of A,
from invcount_A and add inversions of 4 (last
element of B) in the subarray B.
So, invcount_B = invcount_A - 2 + 0
= 3 - 2 + 0
= 1

Same process is repeated for next subarray
and sum of all inversion count is the answer.
```
`// C++ program to count inversions in all sub arrays`
`// of size k using Binary Indexed Tree`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Returns sum of arr[0..index]. This function assumes`
`// that the array is preprocessed and partial sums of`
`// array elements are stored in BITree[].`
`int` `getSum(``int` `BITree[], ``int` `index)`
`{`
`    ``int` `sum = 0; ``// Initialize result`
`    ``// Traverse ancestors of BITree[index]`
`    ``while` `(index > 0) {`
`        ``// Add current element of BITree to sum`
`        ``sum += BITree[index];`
`        ``// Move index to parent node in getSum View`
`        ``index -= index & (-index);`
`    ``}`
`    ``return` `sum;`
`}`
`// Updates a node in Binary Index Tree (BITree) at`
`// given index in BITree.  The given value 'val' is `
`// added to BITree[i] and all of its ancestors in `
`// tree.`
`void` `updateBIT(``int` `BITree[], ``int` `n, ``int` `index, ``int` `val)`
`{`
`    ``// Traverse all ancestors and add 'val'`
`    ``while` `(index <= n) {`
`        ``// Add 'val' to current node of BI Tree`
`        ``BITree[index] += val;`
`        ``// Update index to that of parent `
`        ``// in update View`
`        ``index += index & (-index);`
`    ``}`
`}`
`// Converts an array to an array with values from 1 to n`
`// and relative order of smaller and greater elements `
`// remains same.  For example, {7, -90, 100, 1} is `
`// converted to {3, 1, 4, 2 }`
`void` `convert(``int` `arr[], ``int` `n)`
`{`
`    ``// Create a copy of arrp[] in temp and sort `
`    ``// the temp array in increasing order`
`    ``int` `temp[n];`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``temp[i] = arr[i];`
`    ``sort(temp, temp + n);`
`    ``// Traverse all array elements`
`    ``for` `(``int` `i = 0; i < n; i++) {`
`        ``// lower_bound() Returns pointer to`
`        ``//  the first element greater than `
`        ``// or equal to arr[i]`
`        ``arr[i] = lower_bound(temp, temp + n, `
`                         ``arr[i]) - temp + 1;`
`    ``}`
`}`
`// Returns inversion count of all subarray `
`// of size k in arr[0..n-1]`
`int` `getInvCount(``int` `arr[], ``int` `k, ``int` `n)`
`{`
`    ``int` `invcount = 0; ``// Initialize result`
`    ``// Convert arr[] to an array with values from `
`    ``// 1 to n and relative order of smaller and `
`    ``// greater elements remains same.  For example, `
`    ``// {7, -90, 100, 1} is converted to {3, 1, 4, 2 }`
`    ``convert(arr, n);`
`    ``// Create a BIT with size equal to maxElement+1 `
`    ``// (Extra one is used so that elements can be`
`    ``// directly be used as index)`
`    ``int` `BIT[n + 1];`
`    ``for` `(``int` `i = 1; i <= n; i++)`
`        ``BIT[i] = 0;`
`    ``// Get inversion count of first subarray`
`    ``for` `(``int` `i = k - 1; i >= 0; i--) {`
`        ``// Get count of elements smaller than arr[i]`
`        ``invcount += getSum(BIT, arr[i] - 1);`
`        ``// Add current element to BIT`
`        ``updateBIT(BIT, n, arr[i], 1);`
`    ``}`
`    ``// now calculate the inversion of all other subarrays`
`    ``int` `ans = invcount;`
`    ``int` `i = 0, j = k, icnt = 0, jcnt = 0;`
`    ``while` `(j <= n - 1) {`
`        ``// calculate value of inversion count of first element`
`        ``// in previous subarray`
`        ``icnt = getSum(BIT, arr[i] - 1);`
`        ``updateBIT(BIT, n, arr[i], -1);`
`        ``// calculating inversion count of last element in the`
`        ``// current subarray`
`        ``jcnt = getSum(BIT, n) - getSum(BIT, arr[j]);`
`        ``updateBIT(BIT, n, arr[j], 1);`
`        ``// calculating inversion count of current subarray`
`        ``invcount = invcount - icnt + jcnt;`
`        ``// adding current inversion to the answer`
`        ``ans = ans + invcount;`
`        ``i++, j++;`
`    ``}`
`    ``return` `ans;`
`}`
`int` `main()`
`{`
`    ``int` `arr[] = { 7, 3, 2, 4, 1 };`
`    ``int` `k = 3;`
`    ``int` `n = ``sizeof``(arr) / ``sizeof``(``int``);`
`    ``cout << ``"Number of inversions in all "`
`         ``"subarrays of size "` `<< k <<``" are : "`
`         ``<< getInvCount(arr, k, n);`
`    ``return` `0;`
`}`

Output:

```Number of inversions in all subarrays of size 3 are : 6
```

Time Complexity :- inversion count of first subarray takes O(k log(n)) time and for all other subarray it takes O((n-k)log(n)). So overall time complexity is : O(n log n).
Auxiliary space:- O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Queries on probability of even or odd number in given ranges

Given an array A of size N, containing integers. We have to answer Q queries where each query is of the form:

• K L R : If K = 0, then you have to find the probability of choosing an even number from the segment [L, R] (both inclusive) in the array A.
• K L R : If K = 1, then you have to find the probability of choosing an odd number from the segment [L, R] (both inclusive) in the array A.

For each query print two integers p and q which represent the probability p/q. Both p and q are reduced to the minimal form.
If p is 0 print 0 or if p is equal to q print 1, otherwise print p and q alone.
Examples:

```Input : N = 5, arr[] = { 6, 5, 2, 1, 7 }
query 1: 0 2 2
query 2: 1 2 5
query 3: 0 1 4
Output : 0
3 4
1 2
Explanation :
First query is to find probability of even
element in range [2, 2]. Since range contains
a single element 5 which is odd, the answer
is 0. Second query is to find probability of
odd element in range [2, 5]. There are 3
odd elements in range probability is 3/4.
Third query is for even elements in range
from 1 to 4. Since there are equal even
and odd elements, probability is 2/4
which is 1/2.
```

The idea is to maintain two arrays, say even[] and odd[], which maintain the number of even or odd element upto index i. Now, to answer each query, we can compute result denominator q by finding number of element in the given query range. To find result numerator, we remove number of elements upto l – 1 from elements upto r.
To output the answer in minimal form, we find the GCD of p and q and output p/gcd and q/gcd. For answer 0 and 1, we will explicitly specify the conditions.

Below is C++ implementation of this approach:

`// CPP program to find probability of even`
`// or odd elements in a given range.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Number of tuples in a query`
`#define C 3`
`// Solve each query of K L R form`
`void` `solveQuery(``int` `arr[], ``int` `n, ``int` `Q, `
`                           ``int` `query[][C])`
`{`
`    ``// To count number of odd and even `
`    ``// number upto i-th index.`
`    ``int` `even[n + 1];`
`    ``int` `odd[n + 1];`
`    ``even[0] = odd[0] = 0;`
`    ``// Counting number of odd and even `
`    ``// integer upto index i`
`    ``for` `(``int` `i = 0; i < n; i++) {`
`        ``// If number is odd, increment the `
`        ``// count of odd frequency leave`
`        ``// even frequency same.`
`        ``if` `(arr[i] & 1) {`
`            ``odd[i + 1] = odd[i] + 1;`
`            ``even[i + 1] = even[i];`
`        ``}`
`        ``// If number is even, increment the`
`        ``// count of even frequency leave odd`
`        ``// frequency same.`
`        ``else` `{`
`            ``even[i + 1] = even[i] + 1;`
`            ``odd[i + 1] = odd[i];`
`        ``}`
`    ``}`
`    ``// To solve each query`
`    ``for` `(``int` `i = 0; i < Q; i++) {`
`        ``int` `r = query[i][2];`
`        ``int` `l = query[i][1];`
`        ``int` `k = query[i][0];`
`        ``// Counting total number of element in `
`        ``// current query`
`        ``int` `q = r - l + 1;`
`        ``int` `p;`
`        ``// Counting number of odd or even element `
`        ``// in current query range`
`        ``if` `(k)`
`            ``p = odd[r] - odd[l - 1];`
`        ``else`
`            ``p = even[r] - even[l - 1];`
`        ``// If frequency is 0, output 0`
`        ``if` `(!p)`
`            ``cout << ``"0"` `<< endl;`
`        ``// If frequency is equal to number of  `
`        ``// element in current range output 1.`
`        ``else` `if` `(p == q)`
`            ``cout << ``"1"` `<< endl;`
`        ``// Else find the GCD of both. If yes, `
`        ``// output by dividing both number by gcd`
`        ``// to output the answer in reduced form.`
`        ``else` `{`
`            ``int` `g = __gcd(p, q);`
`            ``cout << p / g << ``" "` `<< q / g << endl;`
`        ``}`
`    ``}`
`}`
`// Driven Program`
`int` `main()`
`{`
`    ``int` `arr[] = { 6, 5, 2, 1, 7 };`
`    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);`
`    ``int` `Q = 2;`
`    ``int` `query[Q][C] = {`
`        ``{ 0, 2, 2 },`
`        ``{ 1, 2, 5 }`
`    ``};`
`    ``solveQuery(arr, n, Q, query);`
`    ``return` `0;`
`}`

Output:

```0
3 4

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Divide an array into k segments to maximize maximum of segment minimums

Given an array of n integers, divide it into k segments and find the maximum of the minimums of k segments. Output the maximum integer that can be obtained among all ways to segment in k subarrays.

Examples:

```Input : arr[] = {1, 2, 3, 6, 5}
k = 2
Output: 5
Explanation: There are many ways to create
two segments. The optimal segments are (1, 2, 3)
and (6, 5). Minimum of both segments are 1 and 5,
hence the maximum(1, 5) is 5.

Input: -4 -5 -3 -2 -1 k=1
Output: -5
Explanation: only one segment, so minimum is -5.
```

There will be 3 cases that need to be considered.

1. k >= 3: When k is greater then 2, one segment will only compose of {max element}, so that max of minimum segments will always be the max.
2. k = 2: For k = 2 the answer is the maximum of the first and last element.
3. k = 1: Only possible partition is one segment equal to the whole array. So the answer is the minimum value on the whole array.

Below is the c++ implementation of the above approach

```// CPP Program to find maximum value of
// maximum of minimums of k segments.
#include <bits/stdc++.h>
using namespace std;

// function to calculate the max of all the
// minimum segments
int maxOfSegmentMins(int a[], int n, int k)
{
// if we have to divide it into 1 segment
// then the min will be the answer
if (k == 1)
return *min_element(a, a+n);

if (k == 2)
return max(a[0], a[n-1]);

// If k >= 3, return maximum of all
// elements.
return *max_element(a, a+n);
}

// driver program to test the above function
int main()
{
int a[] = { -10, -9, -8, 2, 7, -6, -5 };
int n = sizeof(a) / sizeof(a[0]);
int k = 2;
cout << maxOfSegmentMins(a, n, k);
}
```

Output:

`-5`

Time complexity: O(n)
Auxiliary Space: O(1)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Pairs of Positive Negative values in an array

Given an array of distinct integers, print all the pairs having positive value and negative value of a number that exists in the array. We need to print pairs in order of their occurrences. A pair whose any element appears first should be printed first.

Examples:

```Input  :  arr[] = { 1, -3, 2, 3, 6, -1 }
Output : -1 1 -3 3

Input  :  arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 }
Output : -1 1 -4 4 -8 8 -9 9
```

Method 1 (Simple : O(n2))
The idea is to use two nested loop. For each element arr[i], find negative of arr[i] from index i + 1 to n – 1 and store it in another array. For output, sort the stored element and print negative positive value of the stored element.

Below is C++ implementation of this approach:

`// Simple CPP program to find pairs of positive`
`// and negative values present in an array.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Print pair with negative and positive value`
`void` `printPairs(``int` `arr[], ``int` `n)`
`{`
`    ``vector<``int``> v;`
`    ``// For each element of array.`
`    ``for` `(``int` `i = 0; i < n; i++) `
`        ``// Try to find the negative value of `
`        ``// arr[i] from i + 1 to n`
`        ``for` `(``int` `j = i + 1; j < n; j++) `
`            ``// If absolute values are equal print pair.`
`            ``if` `(``abs``(arr[i]) == ``abs``(arr[j])) `
`                ``v.push_back(``abs``(arr[i]));      `
`    ``// If size of vector is 0, therefore there is no `
`    ``// element with positive negative value, print "0"`
`    ``if` `(v.size() == 0)`
`       ``return``;`
`    ``// Sort the vector`
`    ``sort(v.begin(), v.end());`
`    ``// Print the pair with negative positive value.`
`    ``for` `(``int` `i = 0; i < v.size(); i++)`
`        ``cout << -v[i] << ``" "` `<< v[i];    `
`}`
`// Driven Program`
`int` `main()`
`{`
`    ``int` `arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };`
`    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);`
`    ``printPairs(arr, n);`
`    ``return` `0;`
`}`

Output:

```4 4 -8 8 -9 9 -1 1
```

Method 2 (Hahing)
The idea is to use hashing. Traverse the given array, increase the count at absolute value of hash table. If count becomes 2, store its absolute value in another vector. And finally sort the vector. If the size of the vector is 0, print “0”, else for each term in vector print first its negative value and the the positive value.

Below is C++ implementation of this approach:

`// Efficient CPP program to find pairs of `
`// positive and negative values present in`
`// an array.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Print pair with negative and positive value`
`void` `printPairs(``int` `arr[], ``int` `n)`
`{`
`    ``vector<``int``> v;`
`    ``unordered_map<``int``, ``bool``> cnt;`
`    ``// For each element of array.`
`    ``for` `(``int` `i = 0; i < n; i++) {`
`        ``// If element has not encounter early,`
`        ``// mark it on cnt array.`
`        ``if` `(cnt[``abs``(arr[i])] == 0)`
`            ``cnt[``abs``(arr[i])] = 1;`
`        ``// If seen before, push it in vector (`
`        ``// given that elements are distinct)`
`        ``else` `{`
`            ``v.push_back(``abs``(arr[i]));`
`            ``cnt[``abs``(arr[i])] = 0;`
`        ``}`
`    ``}`
`    ``if` `(v.size() == 0)`
`        ``return``;`
`    ``sort(v.begin(), v.end());`
`    ``for` `(``int` `i = 0; i < v.size(); i++)`
`        ``cout << -v[i] << ``" "` `<< v[i] << ``" "``;`
`}`
`// Driven Program`
`int` `main()`
`{`
`    ``int` `arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };`
`    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);`
`    ``printPairs(arr, n);`
`    ``return` `0;`
`}`

Output:

```4 4 -8 8 -9 9 -1 1

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Find single in an array of 2n+1 integer elements

Given an array with 2n+1 integers, n elements appear twice in arbitrary places in the array and a single integer appears only once somewhere inside. Find the lonely integer with O(n) operations and O(1) extra memory.

```Input : { 1, 1, 2, 2, 3, 3, 4, 4, 5}
Output : 5

Input : { 7, 9, 6, 8, 3, 7, 8, 6, 9}
Output : 3
```

The idea is to do XOR of all elements. XOR of all elements gives us the result. The idea is based on below XOR properties.

1. XOR of a number with itself is 0.
2. XOR of a number with 0 is the number.
`// CPP program to find only element in an array`
`// where every element appears twice.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`/* Find non repeating number in an array */`
`int` `findNonRepeating(``int` `arr[], ``int` `n)`
`{`
`    ``int` `res = 0;`
`    ``for` `(``int` `i = 0, res = 0; i < n; i++)`
`        ``res = res ^ arr[i];`
`    ``return` `res;`
`}`
`/* Driver program */`
`int` `main()`
`{`
`    ``int` `arr[] = { 3, 8, 3, 2, 2, 1, 1 };`
`    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);`
`    ``cout << findNonRepeating(arr, n);`
`    ``return` `0;`
`}`

Output:

```8
```

Time Complexity: O(n).
Space Complexity: O(1).

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Check if a given array is pairwise sorted or not

An array is considered pairwise sorted if each successive pair of numbers is in sorted (non-decreasing) order. In case of odd elements, last element is ignored and result is based on remaining even number of elements.

Examples:

```Input : arr[] = {10, 15, 9, 9, 1, 5};
Output : Yes
Pairs are (10, 15), (9,  9) and (1, 5).
All these pairs are sorted in non-decreasing
order.

Input : arr[] = {10, 15, 8, 9, 10, 5};
Output : No
The last pair (10, 5) is not sorted.```

The idea is to traverse array from left to right. Compare elements pairwise, if any pair violates property, we return false. If no pair violates property, we return false.

`// CPP program to check if an array is pair wise`
`// sorted.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Check whether the array is pairwise sorted`
`// or not.`
`bool` `checkPairWiseSorted(``int` `arr[], ``int` `n)`
`{`
`    ``if` `(n==0 || n==1)`
`        ``return` `true``;`
`    ``for` `(``int` `i=0; i<n; i += 2)`
`        ``if` `(arr[i] > arr[i+1])`
`            ``return` `false``;`
`    ``return` `true``;`
`}`
`// Driver program to test above function`
`int` `main() `
`{`
`   ``int` `arr[] = {2, 5, 3, 7, 9, 11};`
`   ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);   `
`   ``if` `(checkPairWiseSorted(arr,n))`
`       ``printf``(``"Yes"``);`
`   ``else`
`       ``printf``(``"No"``);       `
`   ``return` `0;`
`}`

Output:

```Yes
```

Time Complexity: O(n)
Space Complexity: O(1)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Maximum even sum subsequence

Given a array of n positive and negative integers, find the subsequence with the maximum even sum and display that even sum.

Examples:

```Input: arr[] = {-2, 2, -3, 1, 3}
Output: 6
Explanation: The longest subsequence
with even sum is 2, 1 and 3.

Input: arr[] = {-2, 2, -3, 4, 5}
Output: 6
Explanation: The longest subsequence
with even sum is 2, 1 and 3.```

The approach to the problem can be shorted down to points:

1) Sum up all positive numbers
2) If the sum is even then that will be the max sum possible
3) If the sum is not even then either subtract a positive odd number from it, or add a negative odd.
—Find maximum max odd of negative odd numbers, hence sum+a[I] (as a[I] is itself negative)
—Find minimum min odd of positive odd numbers, hence sun-a[I].
—The maximum of the both the results will be the answer.

Below is the implementation of the above approach

`// CPP program to find longest even sum`
`// subsequence.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Returns sum of <a href="#">maximum even sum subsequence</a>`
`int` `maxEvenSum(``int` `arr[], ``int` `n)`
`{`
`    ``// Find sum of positive numbers`
`    ``int` `pos_sum = 0;`
`    ``for` `(``int` `i = 0; i < n; ++i)`
`        ``if` `(arr[i] > 0)`
`            ``pos_sum += arr[i];`
`    ``// If sum is even, it is our`
`    ``// answer`
`    ``if` `(pos_sum % 2 == 0)`
`        ``return` `pos_sum;`
`    ``// Traverse the array to find the`
`    ``// maximum sum by adding a positive`
`    ``// odd or subtracting a negative odd`
`    ``int` `ans = INT_MIN;`
`    ``for` `(``int` `i = 0; i < n; ++i) {`
`        ``if` `(arr[i] % 2 != 0) {`
`            ``if` `(arr[i] > 0)`
`                ``ans = max(ans, pos_sum - arr[i]);`
`            ``else`
`                ``ans = max(ans, pos_sum + arr[i]);`
`        ``}`
`    ``}`
`    ``return` `ans;`
`}`
`// driver program`
`int` `main()`
`{`
`    ``int` `a[] = { -2, 2, -3, 1 };`
`    ``int` `n = ``sizeof``(a) / ``sizeof``(a[0]);`
`    ``cout << maxEvenSum(a, n);`
`    ``return` `0;`
`}`

Output:

`2`

Time complexity : O(n)
Auxiliary Space : O(1)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at