LB_lec10problemSolving.txt

- Find Unique element [https://bit.ly/3y01Zdu ]
- Duplicates in Array [https://bit.ly/3dm6bdZ ]
- Array Intersection [https://bit.ly/3Il0c7n ]
- Pair Sum [https://bit.ly/3EwlU6e ]
- Triplet sum [https://bit.ly/3GbgVs3]
- Sort 0 1 2 [https://bit.ly/3DfQW0s]


1st problem
Find Unique element [https://bit.ly/3y01Zdu ]
int findUnique(int *arr, int size)
{
    //we used the XOR operator to cancel out all the numbers which were the same, leaving out the one which was left in singular (0^s = s and s^s = 0)
    int ans = 0;

    for(int i = 0; i<size; i++)
    {
        ans = ans^arr[i];
    }
    
    return ans;
}

2nd problem
https://leetcode.com/problems/unique-number-of-occurrences/

3rd Problem
Duplicates in Array [https://bit.ly/3dm6bdZ ]
int findDuplicate(vector<int> &arr) 
{
    int ans = 0;

    //XORing all array elements
    for(int i = 0; i<arr.size(); i++)
    {
        ans = ans^arr[i];
    }


    //XORing from 1 to N-1 to the ans variable, 
    //the numbers 1 to N-1 that have occured once got doubled and cancelled
    //out each other, while the remaining number was the one that was 
    //initially occuring twice got left out and stored in the ans variable
	for(int i = 1; i<arr.size(); i++)
    {
        ans = ans^i;
    }
    return ans;
}

4th problem
https://leetcode.com/problems/find-all-duplicates-in-an-array/

5th Problem
Array Intersection [https://bit.ly/3Il0c7n ]

//UNOPTIMIZED SOLUTION, GOT TLE BECAUSE OF O(N^2)
//mini optimization, to break out of operation when the arr1[i] < arr2[j] because we won't find anymore elements like that.

#include <bits/stdc++.h> 
using namespace std;

vector<int> findArrayIntersection(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
	vector<int> ans;
	//checking karna hai
	for(int i =0; i<n; i++){
		int element = arr1[i];

		for(int j =0; j<m; j++){
		
			if (element < arr2[j]) //MINI OPTIMIZATION
			break;
			
			if(element == arr2[j]){
				ans.push_back(element);
				arr2[j]=-1; 
				break;
			} 
		}
	}
	return ans;
}

//OPTIMIZED SOLUTION
//used CASES to solve the problem, see the conditions in the while loop to understand more about what cases I used.
#include <bits/stdc++.h> 
using namespace std;

vector<int> findArrayIntersection(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
	int i = 0, j = 0;
	vector<int> ans;
	//checking karna hai
	//making use of the fact that the given arrays were sorted.
	while(i<n && j<m)
	{
		if(arr1[i]==arr2[j]){
			ans.push_back(arr1[i]);
			i++;
			j++;
		}
		else if (arr1[i] <arr2[j]){
			i++;
		}
		else {
			j++;
		}
	}
	
	return ans;
}


6th Problem
Pair Sum [https://bit.ly/3EwlU6e ]


#include<vector>
using namespace std;
vector<vector<int> > pairSum(vector<int> &arr, int s){
   vector< vector<int> > ans;
   
   for(int i=0;i<arr.size(); i++ )
   {
   		for(int j = i+1; j<arr.size(); j++) {
        	if(arr[i] +arr[j] == s)
            {
            	vector<int> temp;
                temp.push_back(min(arr[i], arr[j]));
                temp.push_back(max(arr[i], arr[j]));
				ans.push_back(temp);
            }
        }
   }
   sort(ans.begin(), ans.end());
   return ans;
}


7th Problem
Triplet sum [https://bit.ly/3GbgVs3]

8th problem
sort 0 1

while arr[i] == 0 -> i++
while arr[j] == 1 -> j--
arr[i] == 1 and arr [j] = 0 state will be automatically reached and hence we swap them and i++ and j--
do all this when i<j

#include<iostream>
using namespace std;

void printArray(int arr[], int n) {
    for(int i=0; i<n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void sortOne(int arr[], int n) {

    int left = 0, right = n-1;

    while(left < right) {

        while(arr[left] == 0 && left < right )  {
            left++;
        }

        while(arr[right]==1 && left < right){
            right--;
        }

        //agar yha pohoch gye ho, iska matlab
        //arr[left]==1 and arr[right]==0
        if(left<right)
        {
            swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }

}

int main() {

    int arr[8] = {1,1,0,0,0,0,1,0};

    sortOne(arr, 8);
    printArray(arr, 8);


    return 0;
}
9th Problem
- Sort 0 1 2 [https://bit.ly/3DfQW0s]