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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide