## 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

#technicalguide

## Program for product of array

Given an array, find product of all array elements.

Examples:

```Input  : ar[] = {1, 2, 3, 4, 5}
Output : 120
Product of array elements is 1 x 2
x 3 x 4 x 5 = 120.

Input  : ar[] = {1, 6, 3}
Output : 18
```
`// C program to find product of array`
`// elements.`
`#include <stdio.h>`
`int` `product(``int` `ar[], ``int` `n)`
`{`
`    ``int` `result = 1;`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``result = result * ar[i];`
`    ``return` `result;`
`}`
`// driver code for the above program`
`int` `main()`
`{`
`    ``int` `ar[] = { 1, 2, 3, 4, 5 };`
`    ``int` `n = ``sizeof``(ar) / ``sizeof``(ar[0]);`
`    ``printf``(``"%d"``, product(a, n));`
`    ``return` `0;`
`}`

Output:

`120`

The above code may cause overflow. Therefore it is always desired to compute product under modulo. The reason of its working is simple distributive property of modulo.

```( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
```

Below is program to find to find and print the product of all the number in this array of Modulo (10^9 +7).

`// C code for above program to find product`
`// under modulo.`
`#include <stdio.h>`
`const` `int` `MOD = 1000000007;`
`int` `product(``int` `ar[], ``int` `n)`
`{`
`    ``int` `result = 1;`
`    ``for` `(``int` `i = 0; i < n; i++)`
`        ``result = (result * ar[i]) % MOD;`
`    ``return` `result;`
`}`
`// driver code for the above program`
`int` `main()`
`{`
`    ``int` `ar[] = { 1, 2, 3, 4, 5 };`
`    ``int` `n = ``sizeof``(ar) / ``sizeof``(ar[0]);`
`    ``printf``(``"%d"``, product(ar, n));`
`    ``return` `0;`
`}`

Output:

```120

```

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

## Next Greater Frequency Element

Given an array, for each element find the value of nearest element to the right which is having frequency greater than as that of current element. If there does not exist an answer for a position, then make the value ‘-1’.

Examples:

```Input : a[] = [1, 1, 2, 3, 4, 2, 1]
Output : [-1, -1, 1, 2, 2, 1, -1]
Explanation:
Given array a[] = [1, 1, 2, 3, 4, 2, 1]
Frequency of each element is: 3, 3, 2, 1, 1, 2, 3
Lets calls Next Greater Frequency element as NGF
1. For element a[0] = 1 which has a frequency = 3,
As it has frequency of 3 and no other next element
has frequency more than 3 so  '-1'
2. For element a[1] = 1 it will be -1 same logic
like a[0]
3. For element a[2] = 2 which has frequency = 2,
NGF element is 1 at position = 6  with frequency
of 3 > 2
4. For element a[3] = 3 which has frequency = 1,
NGF element is 2 at position = 5 with frequency
of 2 > 1
5. For element a[4] = 4 which has frequency = 1,
NGF element is 2 at position = 5 with frequency
of 2 > 1
6. For element a[5] = 2 which has frequency = 2,
NGF element is 1 at position = 6 with frequency
of 3 > 2
7. For element a[6] = 1 there is no element to its
right, hence -1

Input : a[] = [1, 1, 1, 2, 2, 2, 2, 11, 3, 3]
Output : [2, 2, 2, -1, -1, -1, -1, 3, -1, -1]
```

Naive approach:
A simple hashing technique is to use values as index is be used to store frequency of each element. Create a list suppose to store frequency of each number in the array. (Single traversal is required). Now use two loops.
The outer loop picks all the elements one by one.
The inner loop looks for the first element whose frequency is greater than the frequency of current element.
If a greater frequency element is found then that element is printed, otherwise -1 is printed.
Time complexity : O(n*n)

Efficient approach:
We can use hashing and stack data structure to efficiently solve for many cases. A simple hashing technique is to use values as index and frequency of each element as value. We use stack data structure to store position of elements in the array.

1) Create a list to to use values as index to store frequency of each element.
2) Push the position of first element to stack.
3) Pick rest of the position of elements one by one and follow following steps in loop.
…….a) Mark the position of current element as ‘i’ .
……. b) If the frequency of the element which is pointed by the top of stack is greater than frequency of the current element, push the current position i to the stack
……. c) If the frequency of the element which is pointed by the top of stack is less than frequency of the current element and the stack is not empty then follow these steps:
…….i) continue popping the stack
…….ii) if the condition in step c fails then push the current position i to the stack
4) After the loop in step 3 is over, pop all the elements from stack and print -1 as next greater frequency element for them does not exist.

Time complexity is O(n).

Below is the Python 3 implementation of the above problem.

`'''NFG function to find the next greater frequency`
`   ``element for each element in the array'''`
`def` `NFG(a, n):`
`    `
`    ``if` `(n <``=` `0``):`
`        ``print``(``"List empty"``)`
`        ``return` `[]`
`    ``# stack data structure to store the position `
`    ``# of array element `
`    ``stack ``=` `[``0``]``*``n`
`    ``# freq is a dictionary which maintains the `
`    ``# frequency of each element`
`    ``freq ``=` `{}`
`    ``for` `i ``in` `a:`
`        ``freq[a[i]] ``=` `0`
`    ``for` `i ``in` `a:`
`        ``freq[a[i]] ``+``=` `1`
`    ``# res to store the value of next greater `
`    ``# frequency element for each element`
`    ``res ``=` `[``0``]``*``n`
`    ``# initialize top of stack to -1`
`    ``top ``=` `-``1`
`    ``# push the first position of array in the stack`
`    ``top ``+``=` `1`
`    ``stack[top] ``=` `0`
`    `
`    ``# now iterate for the rest of elements`
`    ``for` `i ``in` `range``(``1``, n):`
`        ``''' If the frequency of the element which is `
`            ``pointed by the top of stack is greater `
`            ``than frequency of the current element`
`            ``then push the current position i in stack'''`
`        ``if` `(freq[a[stack[top]]] > freq[a[i]]):`
`            ``top ``+``=` `1`
`            ``stack[top] ``=` `i`
`        ``else``: `
`            ``''' If the frequency of the element which `
`            ``is pointed by the top of stack is less `
`            ``than frequency of the current element, then `
`            ``pop the stack and continuing popping until `
`            ``the above condition is true while the stack`
`            ``is not empty'''`
`            `
`            ``while` `(top>``-``1` `and` `freq[a[stack[top]]] < freq[a[i]]):`
`                ``res[stack[top]] ``=` `a[i]`
`                ``top ``-``=` `1`
`            ``# now push the current element`
`            ``top``+``=``1`
`            ``stack[top] ``=` `i`
`            `
`    ``'''After iterating over the loop, the remaining`
`    ``position of elements in stack do not have the `
`    ``next greater element, so print -1 for them'''`
`    ``while` `(top > ``-``1``):`
`        ``res[stack[top]] ``=` `-``1`
`        ``top ``-``=` `1`
`    ``# return the res list containing next `
`    ``# greater frequency element`
`    ``return` `res`
`# Driver program to test the function`
`print``(NFG([``1``,``1``,``2``,``3``,``4``,``2``,``1``],``7``))`

Output:

```[-1, -1, 1, 2, 2, 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

## 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