Longest Palindrome subsequences

Given a string S="abcdpcba".
The longest palindrome subsequences would be  "abcdcba".

Program:-

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main() {
    string st;
    cin>>st;
    int arr[st.size()][st.size()]={0};
    for(int i=0;i<st.size();i++)
        arr[i][i]=1;
    int len=2;
    while(len<=st.size()){
        for(int i=0;i<st.size()-len+1;i++)
        {
           int j=i+len-1;
            if(st[i]==st[j])
                arr[i][j]=arr[i+1][j-1]+2;
            else arr[i][j]=max(arr[i][j-1],arr[i+1][j]);
        }
        len++;
    }
    cout<<arr[0][st.size()-1]<<endl;
    vector< vector<string> >res;
    res.resize( st.size() , vector<string>( st.size()) );
    for(int i=0;i<st.size();i++)
        res[i][i]=st[i];
     len=2;
    while(len<=st.size()){
        for(int i=0;i<st.size()-len+1;i++)
        {
           int j=i+len-1;
            if(st[i]==st[j] && len==2)
               { string temp;temp+=st[i];
                     temp+=st[j];
                res[i][j]=temp;}
            else if(st[i]==st[j])
                res[i][j]=st[i]+res[i+1][j-1]+st[j];
            else {
                if(res[i][j-1].size() >res[i+1][j].size())
                    res[i][j]=res[i][j-1];
                else res[i][j]=res[i+1][j];
            }       
}
        len++;
    }
    cout<<res[0][st.size()-1]<<"\n";

  return 0;

}

Swapping 3 variable without extra variable

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

int main() {
    int a,b,c;
    cin>>a>>b>>c;

    a=(a+c)-(c=a);
    b=(c+b)-(c=b);

    cout<<a<<" "<<b<<" "<<c;
    return 0;
}

Euler's Totient Function

Euler’s Totient function Φ(n) for an input n is count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.

Program:-

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

int Euler(int n){
    int result = n;
    for(int i=2;i*i<=n;i++){
        if(n%i == 0){
            while(n%i == 0) n = n/i;
            result = result - result/i;
        }
    }
    if(n>1) result = result - result/n;
    return result;
}

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cout<<"Euler Totient of ";
        cout<<i<<" = "<<Euler(i)<<endl;
    }
    return 0;
}

Prime (SieveOfEratosthenes)

Program:-

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

void SieveOfEratosthenes(int n)
{
    vector<bool>prime(n+1,true);
    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*2; i<=n; i += p)
                prime[i] = false;
        }
    }

    for (int p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";
}

int main()
{
    int n;
    cin>>n;
    SieveOfEratosthenes(n);
    return 0;

}

Find the element that appears once (Bit Algorithms)

Example:-

input:- 12, 1, 12, 3, 12, 1, 1, 2, 3, 3

frequency:- 3

ans:- 2

Because other all number except 2 appears more than onces and same number of time. In this program k is other number frequency which are same for all the number except one number. 

Complexity:-
Expected time complexity is O(n) and O(1) extra space.

Program:-

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

class bits{
    int max_size,n,k,result;
    public:
    int *arr;
    bits(int n1,int k1){
        max_size=32;
        k = k1;
        n=n1;
        result=0;
        arr = (int *)malloc(sizeof(int)*n1);
    }
    void input();
    void bitsnumber();
};

void bits::input(){
    for(int i=0;i<n;i++) cin>>arr[i];
}

void bits::bitsnumber(){
    int num,sum=0;
    for(int i=0;i<max_size ;i++){
        num=1<<i;
        sum=0;
        for(int j=0;j<n;j++)
            if(num & arr[j]) sum++;
            if(sum%k) result = result | num;
    }
    cout<<"The number which appears exactly one is: ";
    cout<<result<<endl;
}
int main()
{
    int n,k;
    cout<<"Enter the number of element 'n' and other number which frequency is exactly 'k' times\n";
    cin>>n>>k;
    cout<<"Enter n number\n";
    bits b(n,k);
    b.input();
    b.bitsnumber();
    return 0;
}

Longest Increasing Subsequence (Dynamic Programming)

Program:-

// Note: set(stl c++) don't use if the input are not distinct... 

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

class Lis{
    int size;
    public:
    int *arr;
    Lis(int n){
        size=n;
        arr=(int *)malloc(sizeof(int)*n); 
//arr=new int(n);  See the miracle to uncomment it and comment malloc funtion;
    }
    void input();
    int Lislength();
};

void Lis::input(){
    for(int i=0;i<size;i++) cin>>arr[i];
}

int Lis::Lislength(){
    int j;
    vector<int>vec;
    vec.push_back(arr[0]);
    for(int i=1;i<size;i++)
    {
        for( j=0;j<vec.size();j++)
        {
            if(arr[i]<=vec[j])
            {
                vec[j]=arr[i];
                break;
            }
        }
        if(j==vec.size())
        vec.push_back(arr[i]);
    }
    return vec.size();
}

int main()
{
    int n;
    cin>>n;
    Lis lis(n);
    lis.input();
    cout<<lis.Lislength();
    return 0;
}

Sorting of multiple number in structure of array in Cpp

 Program:-

#include <bits/stdc++.h>
using namespace std;
struct number{
    int a,b,c;
};
static bool comp(struct number aa, struct number ba){
    return aa.a<ba.a;
}

int main() {
    int n;
    cin>>n;
    struct number arr[n];
    for(int i=0;i<n;i++)
    {
      int a,b,c;
        cin>>a>>b>>c;
        arr[i].a=a;
        arr[i].b=b;
        arr[i].c=c;
    }  
    sort(arr,arr+n,comp);
    for(int i=0;i<n;i++)
        cout<<arr[i].a<<" "<<arr[i].b<<" "<<arr[i].c<<endl;
    return 0;
}

Cycle Detection in connected undirected graph using BFS (Implementation using STL Cpp)

Program:-

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

int main() {
    int n,m;
    cin>>n>>m;
    vector<int>vec[n];
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    vector<int>dist(n,-1);
    dist[0]=0;//starting number is always 0..
    queue<int>que;
    que.push(0);
    while(!que.empty()){
        int index=que.front();que.pop();
        for(int i=0;i<vec[index].size();i++){
            if(dist[vec[index][i]]==-1){
                dist[vec[index][i]]=dist[index]+1;
                que.push(vec[index][i]);
            }
          
        }
    }
    if(n==1) cout<<"Not Cycle";
  
    for(int i=1;i<n;i++){
         set<int>st;
        for(int j=0;j<vec[i].size();j++)
            st.insert(dist[vec[i][j]]);
            st.insert(dist[i]);
        if(vec[i].size()>1 && st.size()<=vec[i].size()){ cout<<"Cycle";return 0;}
    }
    cout<<"Not Cycle";
   
    return 0;
}

Cycle Detection in directed graph using DFS (Implementation in STL Cpp)

Program:-

#include <bits/stdc++.h>
using namespace std;
int cycle=0;
void dfs(vector<int>*vec,vector<bool>&vis,int index,vector<bool>&visited){
    if(vis[index]==true) return;
    vis[index]=true;
    visited[index]=true;
    //cout<<index<<" ";
    for(int i=0;i<vec[index].size();i++){
        if(visited[vec[index][i]]) cycle=1;
        if(vis[vec[index][i]]==false){
            dfs(vec,vis,vec[index][i],visited);
        }
       
    }
}

int main() {
    int n,m;
    cin>>n>>m;
    vector<int>vec[n];
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        vec[a].push_back(b);
    }
    vector<bool>vis(n,false);
    for(int i=0;i<n;i++){
        if(vis[i]==false){
            vector<bool>visited(n,false);
            dfs(vec,vis,i,visited);
        }
    }
    if(cycle) cout<<"Cycle";
    else cout<<"Not Cycle";
    return 0;
}

BFS Implementation in cpp

Program:-

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

int main() {
    int n,m;
    cin>>n>>m;
    vector<int>vec[n];
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    vector<int>dist(n,-1);
    dist[0]=0;//starting number is always 0..
    queue<int>que;
    que.push(0);
    while(!que.empty()){
        int index=que.front();que.pop();
        for(int i=0;i<vec[index].size();i++){
            if(dist[vec[index][i]]==-1){
                dist[vec[index][i]]=dist[index]+1;
                que.push(vec[index][i]);
            }
            /*if(dist[vec[index][i]]==dist[index]) {
                cout<<"Biparite Graph\n";
                return 0;
            }*/
        }
    }
    cout<<"Distance from starting vertex\n";
    for(int i=0;i<n;i++) cout<<dist[i]<<" ";
    return 0;
}

DFS Implementation in cpp

 //Program:-

#include <bits/stdc++.h>

using namespace std;
void dfs(vector<int>*vec,vector<bool>&vis,int index){
    if(vis[index]==true) return;
    vis[index]=true;
    cout<<index<<" ";
    for(int i=0;i<vec[index].size();i++){
        if(vis[vec[index][i]]==false){
            dfs(vec,vis,vec[index][i]);
        }
    }
}

int main() {
    int n,m;
    cin>>n>>m;
    vector<int>vec[n];
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    vector<bool>vis(n,false);
    for(int i=0;i<n;i++){
        if(vis[i]==false){
            dfs(vec,vis,i);
            cout<<endl;
        }
    }
   
    return 0;
}

Queue implementation in cpp.

 Program:-

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct Queue{
    int front,rear,size;
    int capacity;
    int *array;
};
struct Queue* createqueue(int capacity)   
{
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->rear = 0;
    queue->size = 0;
    queue->array = new int(capacity);
    return queue;
}   

int isempty(struct Queue *queue)
{
        return (queue->size==0);
}   

int isfull(struct Queue* queue)
{
    return (queue->size==queue->capacity);
}   
void enque(struct Queue* queue , int element)
{
    if(isfull(queue)) return;
    cout<<"Enqueue element is: "<<element<<endl;
    queue->array[(queue->rear++)%queue->capacity] = element;
    queue->size++;
}

void deque(struct Queue *queue)
{
        if(isempty(queue)) return ;
        cout<<"Dequeue element is: "<<queue->array[(queue->front++)%queue->capacity]<<endl;
        queue->size--;
}  

void printf(struct Queue* queue)
{
    while(queue->front!=queue->rear)
    {
        cout<<"The element is: "<<queue->array[(queue->front++)%queue->capacity]<<endl;
    }   
}   
int size(struct Queue* queue)
{
    return queue->size;
}   
int main() {
    struct Queue *queue = createqueue(5);
    enque(queue,10);
    enque(queue,20);
    enque(queue,30);
    deque(queue);
    deque(queue);
    deque(queue);
    cout<<"Size of Queue: "<<size(queue)<<endl;
    enque(queue,40);
    enque(queue,50);
    enque(queue,60);
    enque(queue,70);
    enque(queue,80);
    enque(queue,90);
    printf(queue);
    return 0;
}