## Length of the longest substring with equal 1s and 0s

Given a binary string. We need to find the length of longest balanced sub string. A sub string is balanced if it contains equal number of 0 and 1.

Examples:

```Input : input = 110101010
Output : Length of longest balanced
sub string = 8

Input : input = 0000
Output : Length of longest balanced
sub string = 0
```

simple solution is to use two nested loops to generate every substring. And a third loop to count number of 0s and 1s in current substring. Time complexity of this would be O(n3)

An efficient solution is to use hashing.
1) Traverse string and keep track of counts of 1s and 0s as count_1 and count_0 respectively.
2) See if current difference between two counts has appeared before (We use hashing to store all differences and first index where a difference appears). If yes, then substring from previous appearance and current index has same number of 0s and 1s.

`// CPP for finding length of longest balanced`
`// substring`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// Returns length of the longest substring `
`// with equal number of zeros and ones.`
`int` `stringLen(string str)`
`{`
`    ``// Create a map to store differences`
`    ``// between counts of 1s and 0s.`
`    ``map<``int``, ``int``> m;`
`    `
`    ``// Initially difference is 0.`
`    ``m[0] = -1;   `
`    `
`    ``int` `count_0 = 0, count_1 = 0;`
`    ``int` `res = 0;`
`    ``for` `(``int` `i=0; i<str.size(); i++)`
`    ``{`
`        ``// Keeping track of counts of`
`        ``// 0s and 1s.`
`        ``if` `(str[i] == ``'0'``)`
`            ``count_0++;`
`        ``else`
`            ``count_1++;`
`            `
`        ``// If difference between current counts`
`        ``// already exists, then substring between`
`        ``// previous and current index has same`
`        ``// no. of 0s and 1s. Update result if this`
`        ``// substring is more than current result.`
`        ``if` `(m.find(count_1 - count_0) != m.end())`
`            ``res = max(res, i - m[count_1 - count_0]);`
`            `
`        ``// If current difference is seen first time.        `
`        ``else`
`            ``m[count_1 - count_0] = i;`
`    ``}`
`    ``return` `res;`
`}`
`// driver function`
`int` `main()`
`{`
`    ``string str = ``"101001000"``;`
`    ``cout << ``"Length of longest balanced"`
`            ``" sub string = "``;`
`    ``cout << stringLen(str);`
`    ``return` `0;`
`}`

Output:

```Length of longest balanced sub string = 6
```

Time Complexity : 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

## Largest subarray with equal number of 0s and 1s

Given an array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s. Expected time complexity is O(n).

Examples:

```Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)

Input: arr[] = {1, 1, 1, 1}
Output: No such subarray

Input: arr[] = {0, 0, 1, 1, 0}
Output: 0 to 3 Or 1 to 4
```

Method 1 (Simple)
A simple method is to use two nested loops. The outer loop picks a starting point i. The inner loop considers all subarrays starting from i. If size of a subarray is greater than maximum size so far, then update the maximum size.
In the below code, 0s are considered as -1 and sum of all values from i to j is calculated. If sum becomes 0, then size of this subarray is compared with largest size so far.

`// A simple program to find the largest subarray with equal number of 0s and 1s`
`#include <stdio.h>`
`// This function Prints the starting and ending`
`// indexes of the largest subarray with equal `
`// number of 0s and 1s. Also returns the size `
`// of such subarray.`
`int` `findSubArray(``int` `arr[], ``int` `n)`
`{`
`    ``int` `sum = 0;`
`    ``int` `maxsize = -1, startindex;`
`    ``// Pick a starting point as i`
`    ``for` `(``int` `i = 0; i < n-1; i++)`
`    ``{`
`        ``sum = (arr[i] == 0)? -1 : 1;`
`        ``// Consider all subarrays starting from i`
`        ``for` `(``int` `j = i+1; j < n; j++)`
`        ``{`
`            ``(arr[j] == 0)? sum += -1: sum += 1;`
`            ``// If this is a 0 sum subarray, then `
`            ``// compare it with maximum size subarray`
`            ``// calculated so far`
`            ``if` `(sum == 0 && maxsize < j-i+1)`
`            ``{`
`                ``maxsize = j - i + 1;`
`                ``startindex = i;`
`            ``}`
`        ``}`
`    ``}`
`    ``if` `(maxsize == -1)`
`        ``printf``(``"No such subarray"``);`
`    ``else`
`        ``printf``(``"%d to %d"``, startindex, startindex+maxsize-1);`
`    ``return` `maxsize;`
`}`
`/* Driver program to test above functions*/`
`int` `main()`
`{`
`    ``int` `arr[] =  {1, 0, 0, 1, 0, 1, 1};`
`    ``int` `size = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``findSubArray(arr, size);`
`    ``return` `0;`
`}`

Output:

``` 0 to 5
```

Time Complexity: O(n^2)
Auxiliary Space: O(1)

Method 2 (Tricky)
Following is a solution that uses O(n) extra space and solves the problem in O(n) time complexity.
Let input array be arr[] of size n and maxsize be the size of output subarray.
1) Consider all 0 values as -1. The problem now reduces to find out the maximum length subarray with sum = 0.
2) Create a temporary array sumleft[] of size n. Store the sum of all elements from arr[0] to arr[i] in sumleft[i]. This can be done in O(n) time.
3) There are two cases, the output subarray may start from 0th index or may start from some other index. We will return the max of the values obtained by two cases.
4) To find the maximum length subarray starting from 0th index, scan the sumleft[] and find the maximum i where sumleft[i] = 0.
5) Now, we need to find the subarray where subarray sum is 0 and start index is not 0. This problem is equivalent to finding two indexes i & j in sumleft[] such that sumleft[i] = sumleft[j] and j-i is maximum. To solve this, we can create a hash table with size = max-min+1 where min is the minimum value in the sumleft[] and max is the maximum value in the sumleft[]. The idea is to hash the leftmost occurrences of all different values in sumleft[]. The size of hash is chosen as max-min+1 because there can be these many different possible values in sumleft[]. Initialize all values in hash as -1
6) To fill and use hash[], traverse sumleft[] from 0 to n-1. If a value is not present in hash[], then store its index in hash. If the value is present, then calculate the difference of current index of sumleft[] and previously stored value in hash[]. If this difference is more than maxsize, then update the maxsize.
7) To handle corner cases (all 1s and all 0s), we initialize maxsize as -1. If the maxsize remains -1, then print there is no such subarray.

`// A O(n) program to find the largest subarray `
`// with equal number of 0s and 1s`
`#include <stdio.h>`
`#include <stdlib.h>`
` `
`// A utility function to get maximum of two `
`// integers`
`int` `max(``int` `a, ``int` `b) { ``return` `a>b? a: b; }`
` `
`// This function Prints the starting and ending `
`// indexes of the largest subarray with equal`
`// number of 0s and 1s. Also returns the size`
`// of such subarray.`
`int` `findSubArray(``int` `arr[], ``int` `n)`
`{`
`    ``// variables to store result values`
`    ``int` `maxsize = -1, startindex;  `
` `
`    ``// Create an auxiliary array sunmleft[]. `
`    ``// sumleft[i] will be sum of array `
`    ``// elements from arr[0] to arr[i]`
`    ``int` `sumleft[n];`
`    ``// For min and max values in sumleft[]`
`    ``int` `min, max; `
`    ``int` `i;`
` `
`    ``// Fill sumleft array and get min and max `
`    ``// values in it.  Consider 0 values in arr[]`
`    ``// as -1`
`    ``sumleft[0] = ((arr[0] == 0)? -1: 1);`
`    ``min = arr[0]; max = arr[0];`
`    ``for` `(i=1; i<n; i++)`
`    ``{      `
`        ``sumleft[i] = sumleft[i-1] + ((arr[i] == 0)? `
`                     ``-1: 1);`
`        ``if` `(sumleft[i] < min)`
`            ``min = sumleft[i];`
`        ``if` `(sumleft[i] > max)`
`            ``max = sumleft[i];`
`    ``}`
` `
`    ``// Now calculate the max value of j - i such `
`    ``// that sumleft[i] = sumleft[j]. The idea is `
`    ``// to create a hash table to store indexes of all`
`    ``// visited values.   `
`    ``// If you see a value again, that it is a case of `
`    ``// sumleft[i] = sumleft[j]. Check if this j-i is `
`    ``// more than maxsize. `
`    ``// The optimum size of hash will be max-min+1 as `
`    ``// these many different values of sumleft[i] are`
`    ``// possible. Since we use optimum size, we need `
`    ``// to shift all values in sumleft[] by min before `
`    ``// using them as an index in hash[].`
`    ``int` `hash[max-min+1];`
` `
`    ``// Initialize hash table`
`    ``for` `(i=0; i<max-min+1; i++)`
`        ``hash[i] = -1;`
` `
`    ``for` `(i=0; i<n; i++)`
`    ``{`
`        ``// Case 1: when the subarray starts from `
`        ``//         index 0`
`        ``if` `(sumleft[i] == 0)`
`        ``{`
`           ``maxsize = i+1;`
`           ``startindex = 0;`
`        ``}`
` `
`        ``// Case 2: fill hash table value. If already`
`        ``//         filled, then use it`
`        ``if` `(hash[sumleft[i]-min] == -1)`
`            ``hash[sumleft[i]-min] = i;`
`        ``else`
`        ``{`
`            ``if` `((i - hash[sumleft[i]-min]) > maxsize)`
`            ``{`
`                ``maxsize = i - hash[sumleft[i]-min];`
`                ``startindex = hash[sumleft[i]-min] + 1;`
`            ``}`
`        ``}`
`    ``}`
`    ``if` `(maxsize == -1)`
`        ``printf``(``"No such subarray"``);`
`    ``else`
`        ``printf``(``"%d to %d"``, startindex, startindex+maxsize-1);`
` `
`    ``return` `maxsize;`
`}`
` `
`/* Driver program to test above functions */`
`int` `main()`
`{`
`    ``int` `arr[] =  {1, 0, 0, 1, 0, 1, 1};`
`    ``int` `size = ``sizeof``(arr)/``sizeof``(arr[0]);`
` `
`    ``findSubArray(arr, size);`
`    ``return` `0;`

}

Output:

``` 0 to 5
```

Time Complexity: O(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

## Longest subarray having count of 1s one more than count of 0s

Given an array of size n containing 0’s and 1’s only. The problem is to find the length of the longest subarray having count of 1’s one more than count of 0’s.

Examples:

```Input : arr = {0, 1, 1, 0, 0, 1}
Output : 5
From index 1 to 5.

Input : arr[] = {1, 0, 0, 1, 0}
Output : 1
```

Approach: Following are the steps:

1. Consider all the 0’s in the array as ‘-1’.
2. Initialize sum = 0 and maxLen = 0.
3. Create a hash table having (sum, index) tuples.
4. For i = 0 to n-1, perform the following steps:
1. If arr[i] is ‘0’ accumulate ‘-1’ to sum else accumulate ‘1’ to sum.
2. If sum == 1, update maxLen = i+1.
3. Else check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.
4. Check if (sum-1) is present in the hash table or not. if present, then obtain index of (sum-1) from the hash table as index. Now check if maxLen is less than (i-index), then update maxLen = (i-index).
5. Return maxLen.
`// C++ implementation to find the length of`
`// longest subarray having count of 1's one`
`// more than count of 0's`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// function to find the length of longest`
`// subarray having count of 1's one more`
`// than count of 0's`
`int` `lenOfLongSubarr(``int` `arr[], ``int` `n)`
`{`
`    ``// unordered_map 'um' implemented as`
`    ``// hash table`
`    ``unordered_map<``int``, ``int``> um;`
`    ``int` `sum = 0, maxLen = 0;`
`    ``// traverse the given array`
`    ``for` `(``int` `i = 0; i < n; i++) {`
`        ``// consider '0' as '-1'`
`        ``sum += arr[i] == 0 ? -1 : 1;`
`        ``// when subarray starts form index '0'`
`        ``if` `(sum == 1)`
`            ``maxLen = i + 1;`
`        ``// make an entry for 'sum' if it is`
`        ``// not present in 'um'`
`        ``else` `if` `(um.find(sum) == um.end())`
`            ``um[sum] = i;`
`        ``// check if 'sum-1' is present in 'um'`
`        ``// or not`
`        ``if` `(um.find(sum - 1) != um.end()) {`
`            ``// update maxLength`
`            ``if` `(maxLen < (i - um[sum - 1]))`
`                ``maxLen = i - um[sum - 1];`
`        ``}`
`    ``}`
`    ``// required maximum length`
`    ``return` `maxLen;`
`}`
`// Driver program to test above`
`int` `main()`
`{`
`    ``int` `arr[] = { 0, 1, 1, 0, 0, 1 };`
`    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);`
`    ``cout << ``"Length = "`
`         ``<< lenOfLongSubarr(arr, n);`
`    ``return` `0;`
`}`

Output:

```Length = 5
```

Time Complexity: O(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

## Given an array A[] and a number x, check for pair in A[] with sum as x

Write a C program that, given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.

METHOD 1 (Use Sorting)

Algorithm:

```hasArrayTwoCandidates (A[], ar_size, sum)
1) Sort the array in non-decreasing order.
2) Initialize two index variables to find the candidate
elements in the sorted array.
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second  the rightmost index:  r = ar_size-1
3) Loop while l < r.
(a) If (A[l] + A[r] == sum)  then return 1
(b) Else if( A[l] + A[r] <  sum )  then l++
(c) Else r--
4) No candidates in whole array - return 0
```

Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.
Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.

Example:
Let Array be {1, 4, 45, 6, 10, -8} and sum to find be 16

Sort the array
A = {-8, 1, 4, 6, 10, 45}

Initialize l = 0, r = 5
A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 10
A[l] + A[r] ( -8 + 10) < 2 => increment l. Now l = 1
A[l] + A[r] ( 1 + 10) < 16 => increment l. Now l = 2
A[l] + A[r] ( 4 + 10) < 14 => increment l. Now l = 3
A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)

Note: If there are more than one pair having the given sum then this algorithm reports only one. Can be easily extended for this though.

Implementation:

`# include <stdio.h>`
`# define bool int`
`void` `quickSort(``int` `*, ``int``, ``int``);`
`bool` `hasArrayTwoCandidates(``int` `A[], ``int` `arr_size, ``int` `sum)`
`{`
`    ``int` `l, r;`
`    ``/* Sort the elements */`
`    ``quickSort(A, 0, arr_size-1);`
`    ``/* Now look for the two candidates in the sorted `
`       ``array*/`
`    ``l = 0;`
`    ``r = arr_size-1; `
`    ``while` `(l < r)`
`    ``{`
`         ``if``(A[l] + A[r] == sum)`
`              ``return` `1; `
`         ``else` `if``(A[l] + A[r] < sum)`
`              ``l++;`
`         ``else` `// A[i] + A[j] > sum`
`              ``r--;`
`    ``}    `
`    ``return` `0;`
`}`
`/* Driver program to test above function */`
`int` `main()`
`{`
`    ``int` `A[] = {1, 4, 45, 6, 10, -8};`
`    ``int` `n = 16;`
`    ``int` `arr_size = 6;`
`   `
`    ``if``( hasArrayTwoCandidates(A, arr_size, n))`
`        ``printf``(``"Array has two elements with sum 16"``);`
`    ``else`
`        ``printf``(``"Array doesn't have two elements with sum 16 "``);`
`    ``getchar``();`
`    ``return` `0;`
`}`
`/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING `
`    ``PURPOSE */`
`void` `exchange(``int` `*a, ``int` `*b)`
`{`
`    ``int` `temp;`
`    ``temp = *a;`
`    ``*a   = *b;`
`    ``*b   = temp;`
`}`
`int` `partition(``int` `A[], ``int` `si, ``int` `ei)`
`{`
`    ``int` `x = A[ei];`
`    ``int` `i = (si - 1);`
`    ``int` `j;`
`    ``for` `(j = si; j <= ei - 1; j++)`
`    ``{`
`        ``if``(A[j] <= x)`
`        ``{`
`            ``i++;`
`            ``exchange(&A[i], &A[j]);`
`        ``}`
`    ``}`
`    ``exchange (&A[i + 1], &A[ei]);`
`    ``return` `(i + 1);`
`}`
`/* Implementation of Quick Sort`
`A[] --> Array to be sorted`
`si  --> Starting index`
`ei  --> Ending index`
`*/`
`void` `quickSort(``int` `A[], ``int` `si, ``int` `ei)`
`{`
`    ``int` `pi;    ``/* Partitioning index */`
`    ``if``(si < ei)`
`    ``{`
`        ``pi = partition(A, si, ei);`
`        ``quickSort(A, si, pi - 1);`
`        ``quickSort(A, pi + 1, ei);`
`    ``}`
`}`

Output:

`Array has two elements with the given sum`

METHOD 2 (Use Hash Map)
Thanks to Bindu for suggesting this method and thanks to Shekhu for providing code.
This method works in O(n) time if range of numbers is known.
Let sum be the given sum and A[] be the array in which we need to find pair.

```1) Initialize Binary Hash Map M[] = {0, 0, ...}
2) Do following for each element A[i] in A[]
(a)	If M[x - A[i]] is set then print the pair (A[i], x - A[i])
(b)	Set M[A[i]]
```

Implementation:

`#include <stdio.h>`
`#define MAX 100000`
`void` `printPairs(``int` `arr[], ``int` `arr_size, ``int` `sum)`
`{`
`  ``int` `i, temp;`
`  ``bool` `binMap[MAX] = {0}; ``/*initialize hash map as 0*/`
`  ``for` `(i = 0; i < arr_size; i++)`
`  ``{`
`      ``temp = sum - arr[i];`
`      ``if` `(temp >= 0 && binMap[temp] == 1)`
`         ``printf``(``"Pair with given sum %d is (%d, %d) n"``, `
`                 ``sum, arr[i], temp);`
`      ``binMap[arr[i]] = 1;`
`  ``}`
`}`
`/* Driver program to test above function */`
`int` `main()`
`{`
`    ``int` `A[] = {1, 4, 45, 6, 10, 8};`
`    ``int` `n = 16;`
`    ``int` `arr_size = ``sizeof``(A)/``sizeof``(A[0]);`
`    ``printPairs(A, arr_size, n);`
`    ``getchar``();`
`    ``return` `0;`
`}`

Time Complexity: O(n)
Output:

`Pair with given sum 16 is (10, 6)`

Auxiliary Space: O(R) where R is range of integers.

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

## Count the number of ways to divide an array into three contiguous parts having equal sum

Given a array of n numbers. Our task is to find out the number of ways to divide the array into three contiguous parts such that the sum of three parts is equal. In other words, we need to find the number of index pairs i and j such that sum of elements from 0 to i-1 is equal to sum of elements from i to j is equal to the sum of elements from j+1 to n-1.

Examples:

```Input  : arr[] = {1, 2, 3, 0, 3}
Output : 2
Following are two possible ways to partition
1) Three parts are (0, 1), (2, 2) and (3, 4)
2) Three parts are (0, 1), (2, 3) and (4, 4)

Input : arr[] = {0, 1, -1, 0}
Output : 1
```

If the sum of all the elements of array is not divisible by 3 return 0. Else it is obvious that the sum of each part of each contiguous part will be equal to sum of all elements divided by 3.

Step 1 : Create an array of same size as given array whose i-th index holds the value of sum of elements from indices 0 to i of the given array. Let’s call it prefix array

Step 2 : Create another array of same size as given array whose i-th index the value of sum of elements from indices i to n-1 of the given array. Let’s call it suffix array.

Step 3 : The idea is simple, we start traversing the prefix array and suppose at the i-th index of the prefix array the value of prefix array is equal to (sum of all elements of given array)/3.

Step 4 : For the i found in the above step we look into the suffix array from (i+2)-th index and wherever the value of suffix array is equal to (sum of all elements of given array)/3, we increase the counter variable by 1.

To implement step 4 we traverse suffix array and wherever the value of suffix array is equal to the sum of all elements of given array/3 we push that index of suffix array into the vector. And we do binary search in the vector to calculate number of values in suffix array which are as according to the step 4.

We search in suffix array because there should be at least 1 element between the first and third part.

For more explanation see implementation below

`// C++ program to count number of ways we can`
`// partition an array in three parts with equal`
`// sum.`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// binary search to find the number of required`
`// indices in suffix array. Returns index of`
`// first element which is greater than x.`
`int` `binarysearch(vector <``int``> &v, ``int` `x)`
`{`
`    ``int` `low = 0, high = v.size()-1;`
`    ``while` `(low <= high)`
`    ``{`
`        ``int` `mid = (low + high)/2;`
`        ``if` `(v[mid] <= x)`
`            ``low = mid + 1;`
`        ``else` `if` `(v[mid] > x && v[mid-1] <= x)`
`            ``return` `mid;`
`        ``else` `if` `(v[mid] > x && mid == 0)`
`            ``return` `mid;`
`        ``else`
`            ``high = mid-1;`
`    ``}`
`    ``return` `-1;`
`}`
`// function to calculate the number of ways to`
`// divide the array into three contiguous parts`
`int` `CountContiguousParts(``int` `arr[] ,``int` `n)`
`{`
`    ``int` `count = 0;  ``// initialising answer`
`    ``// Creating and filling  prefix array`
`    ``int` `prefix[n];`
`    ``prefix[0] = arr[0];`
`    ``for` `(``int` `i=1; i<n; i++)`
`        ``prefix[i] = prefix[i-1] + arr[i];`
`    ``// Total sum of elements is equal to last`
`    ``// value in prefix array.`
`    ``int` `total_sum = prefix[n-1];`
`    ``// If sum of all the elements is not dvisible`
`    ``// by 3, we can't divide array in 3 parts of`
`    ``// same sum.`
`    ``if` `(total_sum%3 != 0)`
`        ``return` `0;`
`    ``// Crearing and filling suffix array`
`    ``int` `suffix[n];`
`    ``suffix[n-1] = arr[n-1];`
`    ``for` `(``int` `i=n-2; i>=0; i--)`
`        ``suffix[i] = suffix[i+1] + arr[i];`
`    ``// Storing all indexes with suffix`
`    ``// sum equal to total sum by 3.`
`    ``vector <``int``> v;`
`    ``for` `(``int` `i=0; i<n; i++)`
`        ``if` `(suffix[i] == total_sum/3)`
`            ``v.push_back(i);`
`    ``// Traversing the prefix array and`
`    ``// doing binary search in above vector`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``// We found a prefix with total_sum/3`
`        ``if` `(prefix[i] == total_sum/3)`
`        ``{`
`            ``// Find first index in v[] which`
`            ``// is greater than i+1.`
`            ``int` `res = binarysearch(v, i+1);`
`            ``if` `(res != -1)`
`                ``count += v.size() - res;`
`        ``}`
`    ``}`
`    ``return` `count;`
`}`
`// driver function`
`int` `main()`
`{`
`    ``int` `arr[] = {1 , 2 , 3 , 0 , 3};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``cout << CountContiguousParts(arr, n);`
`    ``return` `0;`
`}`

Output:

```2

```

Time Complexity is 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

## Check if it is possible to sort an array with conditional swapping of adjacent allowed

We are given an unsorted array of integers in the range from 0 to n-1. We are allowed to swap adjacent elements in array many number of times but only if the the absolute difference between these element is 1. Check if it is possible to sort the array.If yes then print “yes” else “no”.

Examples:

```Input : arr[] = {1, 0, 3, 2}
Output : yes
Explanation:- We can swap arr[0] and arr[1].
Again we swap arr[2] and arr[3].
Final arr[] = {0, 1, 2, 3}.

Input : arr[] = {2, 1, 0}
Output : no```

Although the problems looks complex at first look, there is a simple solution to it. If we traverse array from left to right and we make sure elements before an index i are sorted before we reach i, we must have maximum of arr[0..i-1] just before i. And this maximum must be either smaller than arr[i] or just one greater than arr[i]. In first case, we simply move ahead. In second case, we swap and move ahead.

Compare the current element with the next element in array.If current element is greater than next element then do following:-
…a) Check if difference between two numbers is 1 then swap it.
…b) else Return false.
If we reach end of array, we return true.

`// C++ program to check if we can sort`
`// an array with adjacent swaps allowed`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// Returns true if it is possible to sort`
`// else false/`
`bool` `checkForSorting(``int` `arr[], ``int` `n)`
`{`
`    ``for` `(``int` `i=0; i<n-1; i++)`
`    ``{`
`        ``// We need to do something only if`
`        ``// previousl element is greater`
`        ``if` `(arr[i] > arr[i+1])`
`        ``{`
`            ``if` `(arr[i] - arr[i+1] == 1)`
`                ``swap(arr[i], arr[i+1]);`
`            ``// If difference is more than`
`            ``// one, then not possible`
`            ``else`
`                ``return` `false``;`
`        ``}`
`    ``}`
`    ``return` `true``;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``int` `arr[] = {1,0,3,2};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``if` `(checkForSorting(arr, n))`
`       ``cout << ``"Yes"``;`
`    ``else`
`       ``cout << ``"No"``;`
`}`

Output:

```Yes
```

Time Complexity=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

## Find duplicates in a given array when elements are not limited to a range

Given an array of n integers. The task is to print the duplicates in the given array. If there are no duplicates then print -1.

Examples:

```Input : {2, 10, 100, 2, 10, 11}
Output : 2 10

Input : {5, 40, 1, 40, 100000, 1, 5, 1}
Output : 5 40 1
```

Note:The duplicate elements can be printed in any order.

Simple Approach: By using two loops. It has a time complexity of O(n2).

Efficient Approach: Use unordered_map for hashing. Count frequency of occurrence of each element and the elements with frequency more than 1 is printed. unordered_map is used as range of integers is not known.

`// C++ program to find`
`// duplicates in the given array`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// function to find and print duplicates`
`void` `printDuplicates(``int` `arr[], ``int` `n)`
`{`
`    ``// unordered_map to store frequencies`
`    ``unordered_map<``int``, ``int``> freq;`
`    ``for` `(``int` `i=0; i<n; i++)`
`        ``freq[arr[i]]++;`
`    ``bool` `dup = ``false``;`
`    ``unordered_map<``int``, ``int``>:: iterator itr;`
`    ``for` `(itr=freq.begin(); itr!=freq.end(); itr++)`
`    ``{`
`        ``// if frequency is more than 1`
`        ``// print the element`
`        ``if` `(itr->second > 1)`
`        ``{`
`            ``cout << itr->first << ``" "``;`
`            ``dup = ``true``;`
`        ``}`
`    ``}`
`    ``// no duplicates present`
`    ``if` `(dup == ``false``)`
`        ``cout << ``"-1"``;`
`}`
`// Driver program to test above`
`int` `main()`
`{`
`    ``int` `arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11};`
`    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);`
`    ``printDuplicates(arr, n);`
`    ``return` `0;`
`}`

Output:

```12 11 5
```

Time Complexity: 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

## Number of subarrays for which product and sum are equal

Given a array of n numbers. We need to count the number of subarrays having the product and sum of elements are equal
Examples:

```Input  : arr[] = {1, 3. 2}
Output : 4
The subarrays are :
[0, 0] sum = 1, product = 1,
[1, 1] sum = 3, product = 3,
[2, 2] sum = 2, product = 2 and
[0, 2] sum = 1+3+2=6, product = 1*3*2 = 6

Input : arr[] = {4, 1, 2, 1}
Output : 5```

The idea is simple, we check for each subarray that if product and sum of its elements are equal or not. If it is then increase the counter variable by 1

`// C++ program to count subarrays with`
`// same sum and product.`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`// returns required number of subarrays`
`int` `numOfsubarrays(``int` `arr[] , ``int` `n)`
`{`
`    ``int` `count = 0; ``// Initialize result`
`    ``// checking each subarray`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``int` `product = arr[i];`
`        ``int` `sum = arr[i];`
`        ``for` `(``int` `j=i+1; j<n; j++)`
`        ``{`
`            ``// checking if product is equal`
`            ``// to sum or not`
`            ``if` `(product==sum)`
`                ``count++;`
`            ``product *= arr[j];`
`            ``sum += arr[j];`
`        ``}`
`        ``if` `(product==sum)`
`            ``count++;`
`    ``}`
`    ``return` `count;`
`}`
`// driver function`
`int` `main()`
`{`
`    ``int` `arr[] = {1,3,2};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``cout << numOfsubarrays(arr , n);`
`    ``return` `0;`
`}`

Output:

```4
```

Time Complexity : O(n2)\

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

## Program for multiplication of array elements

We are given an array and we have to calculate the product of an array using both iterative and recursive method.

Examples:

```Input : array[] = {1, 2, 3, 4, 5, 6}
Output : 720
Here, product of elements = 1*2*3*4*5*6 = 720

Input : array[] = {1, 3, 5, 7, 9}
Output : 945```

Iterative Method :
We initialize result as 1. We traverse array from left to right and multiply elements with result.

`// Iterative C++ program to multiply array elements`
`#include<iostream>`
`using` `namespace` `std;`
`// Function to calculate the product of the array`
`int` `multiply(``int` `array[], ``int` `n)`
`{`
`    ``int` `pro = 1;`
`    ``for` `(``int` `i=0;i<n;i++)    `
`        ``pro = pro * array[i];`
`    ``return` `pro;`
`}`
`// Driver function`
`int` `main()`
`{`
`    ``int` `array[] = {1, 2, 3, 4, 5, 6};`
`    ``int` `n = ``sizeof``(array)/``sizeof``(array[0]);`
`    ``//Function call to calculate product`
`    ``cout<<multiply(array, n);`
`    ``return` `0;`
`}`

Output:

`720`

Recursive Method :

`// Recursive C++ program to multiply array elements`
`#include<iostream>`
`using` `namespace` `std;`
`// Function to calculate the product of `
`// array using recursion`
`int` `multiply(``int` `a[], ``int` `n)`
`{`
`    ``// Termination condition`
`    ``if` `(n==0)`
`        ``return``(a[n]);`
`    ``else`
`        ``return` `(a[n] * multiply(a,n-1));`
`}`
`// Driver function`
`int` `main()`
`{`
`    ``int` `array[] = {1, 2, 3, 4, 5, 6};`
`    ``int` `n = ``sizeof``(array)/``sizeof``(array[0]);`
`    ``//Function call to calculate the product`
`    ``cout << multiply(array, n-1) << endl;`
`    ``return` `0;`
`}`
``` 720

```

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

## Convert characters of a string to opposite case

Given a string, convert the characters of the string into opposite case,i.e. if a character is lower case than convert it into upper case and vice-versa.
Examples:

```Input : TechCodeBit
Output : tECHcODEbIT

Input : hello every one
Output : HELLO EVERY ONE
```

ASCII values  of alphabets: A – Z = 65 to 90, a – z = 97 to 122
Steps:

1. Take one string of any length and calculate its length.
2. Scan string character by character and keep checking  the index .
• If character in a index is in lower case, then subtract 32 to convert it in upper case, else add 32 to convert it in upper case
3. Print the final string.
`// CPP program to Convert characters `
`// of a string to opposite case`
`#include<iostream>`
`using` `namespace` `std;`
` `
`// Function to convert characters `
`// of a string to opposite case`
`void` `convertOpposite(string &str)`
`{`
`    ``int` `ln = str.length();`
`     `
`    ``// Conversion according to ASCII values`
`    ``for` `(``int` `i=0; i<ln; i++)`
`    ``{`
`        ``if` `(str[i]>=``'a'` `&& str[i]<=``'z'``)`
`        ``//Convert lowercase to uppercase`
`            ``str[i] = str[i] - 32;`
`        ``else` `if``(str[i]>=``'A'` `&& str[i]<=``'Z'``)`
`        ``//Convert uppercase to lowercase`
`            ``str[i] = str[i] + 32;`
`    ``}`
`}`
` `
`// Driver function`
`int` `main()`
`{`
`    ``string str = ``"<a href="``#``">TechCodeBit</a>"``;`
`     `
`    ``// Calling the Function`
`    ``convertOpposite(str);`
`     `
`    ``cout << str;`
`    ``return` `0;`
`}`

Output:

tECHcODEbIT

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