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

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

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

Examples:

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

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

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

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

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

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

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

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

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

For more explanation see implementation below

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

Output:

2

Time Complexity is O(n log n)

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

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

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

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

Examples:

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

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

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

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

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

Output:

Yes

Time Complexity=O(n)

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

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

 

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

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

Examples:

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

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

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

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

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

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

Output:

12 11 5

Time Complexity: O(n)

 

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

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

Number of subarrays for which product and sum are equal

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

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

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

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

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

Output:

4

Time Complexity : O(n2)\

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

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

Program for multiplication of array elements

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

Examples:

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

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

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

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

Output:

720

 

Recursive Method :

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


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

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

Convert characters of a string to opposite case

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

Input : TechCodeBit
Output : tECHcODEbIT

Input : hello every one
Output : HELLO EVERY ONE

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

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

Output:

tECHcODEbIT

 

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

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