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

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

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

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