Add

Array Coding 5 Problems for Interviews


1.Subarrays with equal 1s and 0s

Given an array containing 0s and 1s. Find the number of subarrays having equal number of 0s and 1s.

Example 1:

Input:
n = 7
A[] = {1,0,0,1,0,1,1}
Output: 8
Explanation: The index range for the 8 
sub-arrays are: (0, 1), (2, 3), (0, 3), (3, 4), 
(4, 5) ,(2, 5), (0, 5), (1, 6)

Example 2:

Input:
n = 5
A[] = {1,1,1,1,0}
Output: 1
Explanation: The index range for the 
subarray is (3,4).

C++ Solution

Execution Time -: 0.5

class Solution{
  public:
    //Function to count subarrays with 1s and 0s.
    long long int countSubarrWithEqualZeroAndOne(int arr[], int n)
    {
        //Your code here
        unordered_map<int,int> hashmap;
int sum=0,count=0;
        for(int i=0;i<n;i++){
            if(arr[i]==0)
                arr[i]=-1;
        }
        for(int i=0;i<n;i++){
            sum+=arr[i];
            if(sum==0)
                count++;
            if(hashmap[sum])
                count+=hashmap[sum];
            hashmap[sum]++;   
        }
        return count;
    }
};
unordered_map<int,int>s1;
        int prefix_sum=0;     
        int count=0;
        for(int i=0;i<n;i++){
            if(arr[i]==0){
                arr[i]=-1;
            }
             prefix_sum+=arr[i];
            s1[prefix_sum]++;
        }
        for(auto x:s1){
          int c=x.second;
        count+=c*(c-1)/2;
        if( x.first==0)
        count+=x.second;
      }
        return count;
}
   pro tip--replace all 0 to -1 and count the pairs with sum=0;

 
2.Alternate positive and negative numbers 
 
Given an unsorted array Arr of N positive and negative numbers. Your task is to create an array of alternate positive and negative numbers without changing the relative order of positive and negative numbers.
 
Example 1:
 
Input: 
N = 9
Arr[] = {9, 4, -2, -1, 5, 0, -5, -3, 2}
Output:
9 -2 4 -1 5 -5 0 -3 2
 
Example 2:
 
Input: 
N = 10
Arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
Output:
5 -5 2 -2 4 -8 7 1 8 0
 
void rearrange(int arr[], int n) {
    // code here
       vector<int> pos, neg;
       for(int i=0;i<n;i++){
           if(arr[i]>=0){
               pos.push_back(arr[i]);
           }
           else{
               neg.push_back(arr[i]);
           }
       }
       int nx = pos.size(), mx = neg.size();
       int i=0, j=0, a=0;
       while(i<nx||j<mx){
 
 if(i<nx){
               arr[a++]=pos[i];
               i++;
           }
           if(j<mx){
               arr[a++]=neg[j];
               j++;
           }
       }
}
 
void rearrange(int a[], int n) {
              vector<int>nega,posi,ans;
              for(int i=0;i<n;i++){
                  if(a[i]<0) nega.push_back(a[i]);
                  else posi.push_back(a[i]);        
              }             
              int i =0,j=0,k=0;
              while(i<posi.size() && j<nega.size()){
                  a[k++]=posi[i++];
                  a[k++]=nega[j++];
              }
while(i<posi.size())
              a[k++]=posi[i++];
              while(j<nega.size())
              a[k++]=nega[j++];    
          }

 
3.Subarray with 0 sum
 
Given an array of positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.
 
Example 1:
 
Input:
 
5
 
4 2 -3 1 6 
 
Output: 
 
Yes
 
Explanation: 
 
2, -3, 1 is the subarray 
 
with sum 0.
 
Example 2:
 
Input:
5
4 2 0 1 6
Output: 
Yes
Explanation: 
0 is one of the element 
in the array so there exist a 
subarray with sum 0.
 
accepted Logic:- a1+a2+a3+subarray with zero sum = a1+a2+a3
 
bool subArrayExists(int arr[], int n)
    {
        set<int>s;
        int sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=arr[i];
            if(sum==0)return 1;
            if(s.find(sum)!=s.end())return 1;
else s.insert(sum);
        }
        return 0;
    }
class Solution{
    public:
    //Complete this function
    //Function to check whether there is a subarray present with 0-sum or not.
    bool subArrayExists(int arr[], int n)
    {
        //Your code here
        unordered_set<int>hashset;
        int sum=0;
for(int i=0;i<n;i++){
            sum+=arr[i];
            if(hashset.find(sum)!=hashset.end()){
                return true;
            }else if(sum==0){
                return true;
            }else{
                hashset.insert(sum);
            }
        }
        return false;
    }
};
 
 
4.Kadane's Algorithm 
 
Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.
 
Example 1:
 
Input:
N = 5
Arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which 
is a contiguous subarray.
 
Example 2:
 
Input:
N = 4
Arr[] = {-1,-2,-3,-4}
Output:
-1
Explanation:
Max subarray sum is -1 
of element (-1)
 
long maxSubarraySum(int arr[], int n){
       long max=Long.MIN_VALUE;
       for(int i=0;i<n;i++) {
           for(int j=i;j<n;j++) {
               long sum=0;
               for(int k=i;k<=j;k++) {
                   sum += arr[k];
               }
               if(sum>max) {
                   max=sum;
               }
           }
       }
 
return max;
       
   }
 
 
 
long long maxSubarraySum(int a[], int n){
       long long mxSum=a[0];
       int ct=0;
       long long curr=0;
       for(int i=0; i<n; i++) {
           curr = curr + a[i];       
           if(curr > mxSum)
             mxSum=curr;
           
           if(curr<0){
 
 curr=0;
            ct++;
           }
       }
       
       if(ct!=n)
        return mxSum;
       else
       {
           mxSum=a[0];
           for(int i=0; i<n; i++)
           {
 
mxSum=max(mxSum , (long long )a[i]);
           }
           return mxSum;
       }
   }
 
5.Factorials of large numbers
 
Given an integer N, find its factorial.
Example 1:
 
Input: N = 5
Output: 120
Explanation : 5! = 1*2*3*4*5 = 120
 
Example 2:
 
Input: N = 10
Output: 3628800
Explanation :
10! = 1*2*3*4*5*6*7*8*9*10 = 3628800
 
#include<iostream>
using namespace std;
int main()
{
   int i;
  int fact=1;
 long int n;
 cin>>n;
 for(i=n;i>=1;i--)
 {
     fact=fact*i;
 }
 cout<<fact;
 
 return 0;
}
 
vector<int> ret;
        ret.push_back(1);
        for(int i = 2 ; i <= N ; i ++){
            int car = 0;
            for(int j = ret.size() - 1; j >= 0 ;j--){
                int value = ret[j] * i + car;
                ret[j] = value %10;
                car  = value / 10;
            }
            while(car > 0){
                ret.insert(ret.begin(),car %10);
                car /= 10;
}
        }
        return ret;









Tags

































Post a Comment

0
Comments



* Please Don't Spam Here. All the Comments are Reviewed by Admin.