FIND THE PAIR IN AN ARRAY FOR A GIVEN SUM USING HASH TECHNIQUE(OPTIMIZED)

Hii friends,here find the optimize version of the above problem.If u have any doubt let me know

#include<bits/stdc++.h>
using namespace std;
int main(){

  int n,i,j;
  cout << "Enter the size of array:\n";
  cin >> n;
  int arr[n];

  cout << "Enter the elements of array:\n";
  for(i=0;i<n;i++){
   cin >> arr[i];
  }

  int sum;
  cout << "Enter the value of sum:\n";
  cin>> sum;

  //Using hash technique
  map<int,int> hash;
  for(i=0;i<n;i++){
   hash[arr[i]]=1;
  }

  for(i=0;i<n;i++){
   if(hash.find(sum-arr[i])!=hash.end()){
    cout << arr[i] << " " << sum-arr[i] << endl;

    hash.erase(arr[i]);//to remove duplicates pair
   }
  }




 return 0;
}

FIND THE PAIR IN AN ARRAY FOR A GIVEN SUM

Hii friends,this method is simple brute force i think when interviewer asks you this questions then this solution must come in your mind then u can optimise this So right now i am just posting this brute force solution later i will upload its optimize version. Optimized Version

#include<bits/stdc++.h>
using namespace std;
int main(){

  int n,i,j;
  cout << "Enter the size of array:\n";
  cin >> n;
  int arr[n];

  cout << "Enter the elements of array:\n";
  for(i=0;i<n;i++){
   cin >> arr[i];
  }

  int sum;
  cout << "Enter the value of sum:\n";
  cin>> sum;

  for(i=0;i<n;i++){
   for(j=i+1;j<n;j++){
    if((arr[i]+arr[j])==sum){
     cout << arr[i] << " " << arr[j] << endl;
    }
   }
  }




 return 0;
}

FIND THE PAIR IN AN ARRAY FOR A GIVEN SUM(USING TWO POINTER CONCEPT) VERY GOOD METHOD

Hi,guys here is the best solution for this problem. Time Complexity:o(nlogn) Space Complexity:o(1) If u have any doubt plz comment below.

#include<bits/stdc++.h>
using namespace std;
int main(){

  int n,i,j;
  cout << "Enter the size of array:\n";
  cin >> n;
  int arr[n];

  cout << "Enter the elements of array:\n";
  for(i=0;i<n;i++){
   cin >> arr[i];
  }

  int sum;
  cout << "Enter the value of sum:\n";
  cin>> sum;

  //Using Two pointer concept

  //first of all sort the array
  sort(arr,arr+n);

  i=0;//1st element
  j=n-1;//last element
  while(i<j){
   int x=arr[i]+arr[j];
   if(x==sum){
    cout << arr[i] << " " << arr[j] << endl;
    i++;
    j--;
   }
   else if(x>sum){
    j--;
   }
   else{
    i++;
   }
  }
  



 return 0;
}

find the number occuring odd number of times

Hi,guys here is the simple solution(brute force approach). Time complexity:o(n^2) Space Complexity:o(1)

#include<bits/stdc++.h>
using namespace std;
int main(){
 int i,j,n;
 cout << "Enter the size of array:\n";
 cin >> n;

 int arr[n];
 //note that there is only one element which occure odd number of times
 cout << "Enter the elements of array:\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 //brute force approach
 for(i=0;i<n;i++){
  int count=0;
  for(j=0;j<n;j++){
   if(arr[i]==arr[j]){
    count++;
   }
  }
  if(count%2==1){
   cout << arr[i] ;
   break;
  }
 }
}

Hi,firends we can also solve the above problem using Hash technique: Time Complexity:o(n) Space Complexity:o(n) Here is the code:

#include<bits/stdc++.h>
using namespace std;
int main(){
 int i,j,n;
 cout << "Enter the size of array:\n";
 cin >> n;

 int arr[n];
 //note that there is only one element which occure odd number of times
 cout << "Enter the elements of array:\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 //using hash technique
 map<int,int> hash;
 for(i=0;i<n;i++){
  hash[arr[i]]++;
 }

 map<int,int>::iterator it;
 for(it=hash.begin();it!=hash.end();it++){
  if((it->second)%2==1){
   cout << it->first << endl;
   break;
  }
 }
}

Hi,guys but this above method is not optimise .

Concept:
The approach for this method is using XOR operation.

.XOR truth table:
1 XOR 1=0
0 XOR 0=0
1 XOR 0=1
0 XOR 1=1

.from xor truth table we can say that xor of a number the same number give 0 as result.

example:
4 XOR 4=0

Conclusion ::
if we take xor of a number with itself even number of times it gives 0.
but if we take xor of a number with itself odd number of times it gives number itself.

Here is the below code.still u have any doubt plz comment below.
Time Complexity:o(n)
Space Complexity:o(1)

#include<bits/stdc++.h>
using namespace std;
int main(){
 int i,j,n;
 cout << "Enter the size of array:\n";
 cin >> n;

 int arr[n];
 //note that there is only one element which occure odd number of times
 cout << "Enter the elements of array:\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 //using XOR operation
 int ans;
 ans=arr[0];
 for(i=1;i<n;i++){
  ans=ans^arr[i];
 }

 cout << ans << endl;
}

FIND MAJORITY ELEMENT IN AN ARRAY

Hi,friends this is very famous problem for interview purpose.

Question:What is majority element?
Ans:a element that appear more than (n/2)times in an array of size (n).

example: Arr:3 3 4 2 4 4 2 4 4
         Here n=9
         So n/2=4
         so majority element is a element that appear more than 4
         Here majority element is : 4(bcoz its count is 5).

 Simple Brute force approach is given below:
 Time complexity:o(n^2)
 Space complexity:o(1)

 If u have any doubt plz comment below:

 

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin >> n;

 int arr[n];
 cout << "Enter the elements of array:\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 for(i=0;i<n;i++){
  int count =0;
  for(j=0;j<n;j++){
   if(arr[i]==arr[j]){
    count++;
   }
  }
  if(count>(n/2)){
   cout << "majority element is:" << arr[i] ;
   break; 
  }
 }
 return 0;
}

Hi guys this is optimization for the majority element problem 
Time Complexity:o(n)
Space Complexity:o(1)

This code is based on the moore's voting algorithm:

Concept:
>step1:first of all we are simply taking 1st element as majority element and also one variable which shows how many time that element hash occured
>till now.
>step2:Now we are comparing array element with majority element if they are same then increse the count variable by 1
->else decrease count variable by 1
>step3:Now check if count is 0 then update maj_element and make its count 1.

If u guys still have doubt plz comment below

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin >> n;

 int arr[n];
 cout << "Enter the elements of array:\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 int maj_ele_index=0;
 int count=1;

 for(i=1;i<n;i++){
  if(arr[maj_ele_index]==arr[i]){
   count++;
  }
  else{
   count--;
   if(count==0){
    maj_ele_index=i;
    count=1;
   }
  }
 }

 //find the occurence of maj_element
 count=0;
 for(i=0;i<n;i++){
  if(arr[i]==arr[maj_ele_index]){
   count++;
  }
 }

 if(count>(n/2)){
  cout << "majority Element is:\n" << arr[maj_ele_index];
 }
 else{
  cout << "There is no element which occur more than n/2";
 }
 return 0;
}

LARGEST SUM CONTIGUOUS SUBARRAY

Hi,guys this is one of my favourite problem.
During my campus placement 2 or 3 interviewer ask me this question.

So first thing what the problem is:
example :arr[]={-2,-3,4,-1,-2,1,5,-3};
we have to find the largest sum that is possible in contiguous subarray

Here largest sum is 7(and subarray is (4,-1,-2,1,5)).
All other combination of subarray has sum less than 7.

Here is the simple brute force approach:
Its time complexity is:o(n^2)
space complexity:o(1) 

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin>> n;

 int arr[n];
 cout << "Enter elements of array\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 int max_so_far=0;
 for(i=0;i<n;i++){
  int current_sum=0;
  for(j=i;j<n;j++){
   current_sum+=arr[j];
   if(max_so_far<current_sum){
   max_so_far=current_sum;
  }
  }
  
 }

 cout << "maximum sum is:" << max_so_far;
 return 0;
}

Hey this is the optimization of above problem;

algorithm: kadane algorithm

Time Complexity:o(n)
Space Complexity:o(1)

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin>> n;

 int arr[n];
 cout << "Enter elements of array\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 int max_so_far=0;
 int curr_sum=0;

 int count=0;
 for(i=0;i<n;i++){
  if(arr[i]>0){
   count++;
  }
 }

 if(count==0){
  //means all elements are negative in array
  //so ans is simply maximum of array

  max_so_far=arr[0];
  for(i=1;i<n;i++){
   if(max_so_far<arr[i]){
    max_so_far=arr[i];
   }
  }
  cout << "maximum sum is:" << max_so_far;


 }
 else{
  for(i=0;i<n;i++){
   curr_sum+=arr[i];

   if(curr_sum<0){
    curr_sum=0;
   }
   
   if(max_so_far<curr_sum){
    max_so_far=curr_sum;
   }


  }



  cout << "maximum sum is:" << max_so_far;

 }

 
 return 0;
}

SORT AN ARRAY OF 0'S ,1'S AND 2'S

Hey friends this is one of the easy problem but it is important for interview purpose:

problem: we have an array of 0's , 1's , 2's. we have to sort the array in o(n) time.

example: arr[]={2,1,0,2,0,2,1};
after sorting arr[] should be :{0,0,1,1,2,2,2};

Time Complexity:o(n)
Space Complexity;o(1)

Here is the code for the problem if u have any doubt let me know:

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin >> n;

 int arr[n];
 cout << "Enter the elements of array:\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 //I am taking 3 variable for the count of 0's and 1's and 2's.
 int count_0=0;
 int count_1=0;
 int count_2=0;

 for(i=0;i<n;i++){
  if(arr[i]==0){
   count_0++;
  }
  else if(arr[i]==1){
   count_1++;
  }
  else{
   count_2++;
  }
 }

 i=0;
 while(count_0>0){
  arr[i++]=0;
  count_0--;
 }

 while(count_1>0){
  arr[i++]=1;
  count_1--;
 }

 while(count_2>0){
  arr[i++]=2;
  count_2--;
 }

 cout << "finally the array is :\n";
 for(i=0;i<n;i++){
  cout << arr[i] << " ";
 }

 return 0;
}