Author Arunima Mandal

Binary Search

Arunima Mandal Leave a comment

Note:

Binary Search is a core algorithm of Computer Science. It can be found everywhere but I am particularly writing it here as I just got to know about new knowledge or change in the logic of the traditional algorithm. The algorithm has been made more appropriate recently with the memory and capacity evolving in recent age. For detail and in-depth knowledge please see this – https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

So basically in the traditional algorithm while dividing the array or vector space into two halves, the proper logic would be –

mid = first+(last-first)/2;

instead of 

mid = (first+last)/2;

Otherwise, you would get a runtime error in the case that the sum of the first and last is

greater than the maximum positive int value (231 – 1). 

Code:

#include <bits/stdc++.h>

using namespace std;

int a[10000007];
int not_found_pos=-1; //Declaring it global to get the index if the item is not found

bool binarySearch(int item, int n) 
{
    int first=0, last=n-1, mid=0;
    while(first<=last)
    {
        mid=first+(last-first)/2; //for avoiding overflow of summation of first and last
        if(item>a[mid]) first=mid+1;
        else if(item<a[mid]) last=mid-1;
        else return mid; //item=a[mid] //item found
    }
    //Item was not found
    not_found_pos=first; //But if it was found it would be at index 'first'
    return -1; 
}

int main()
{
    int n,item;
    cin>>n;
    for(int i=0; i<n; i++) cin>>a[i]; // Must be sorted.
    cout<<"Enter the item that to be searched"<<endl;
    cin>>item;
    int pos=binarySearch(item,n);
    if(pos==-1)
    {
        cout<<"The item "<<item<<" was not found but if it was found, it would be at index "<< not_found_pos << endl;
    }
    else //Assuming Indexing from "0"
    {
        cout<<"The item "<<item<<" was found at position "<<pos<<endl;
    }
    return 0;
}

Codeforces Round #797 (Div. 3) – D. Black and White Stripe

Arunima Mandal Leave a comment

Problem Link:
https://codeforces.com/contest/1690/problem/D
Note: This is quite an interesting problem for cumulative sum or prefix sum.
Solution

#include <bits/stdc++.h>

using namespace std;

int a[200005];
queue<int> q;
int main ()
{
    int t;
    cin>>t;
    int n,k;
    string s;

    for(int z=0;z<t; z++)
    {
        cin>>n>>k;
        cin>>s;
        bool d=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i-1]=='W') a[i]=a[i-1]+1;
            else a[i]=a[i-1];
        }
        int mini=20000005;
        for(int i=k;i<=n;i++)
        {
            mini=min(mini,a[i]-a[i-k]);
        }
        cout<<mini<<endl;
    }

    return 0;
}

UVA – 673 – Parentheses Balance

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/6/673.pdf

Note:
This can be solved using different data structures and logic. I have used Stack to approach the problem.

Solution:

/*
Author: Arunima Mandal
Updated Date: 06.16.2020
*/
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long,long>
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forrev(i,n) for(int i=n-1; i>=0; i--)
#define forab(i,a,b) for(int i=a;i<=b;i++)
#define forba(i,b,a) for(int i=b;i>=a;i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 1000006
#define inf 100000008
ll power(int n,int p)
{
ll ans=1;
for1(i,p) ans*=n;
return ans;
}
ll m=1000001;
ll bigmod(ll n,ll p)
{
if(p==0) return 1;
else if(p%2==0)
{
ll x=(bigmod(n,p/2))%m;
return (x*x)%m;
}
else return ((n%m)*(bigmod(n,p-1)%m))%m;
}
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
stack<char> st;
string s;
int main()
{
// CIN; //if getline() is present, it can't be used.
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t,d;
sf(t);
getchar();
for0(z,t)
{
getline(cin,s);
d=0;
for0(i,sz(s))
{
if(s[i]=='(' || s[i]=='{' || s[i]=='[')
{
st.push(s[i]);
}
else if(s[i]==' ') continue;
else
{
if(!st.empty())
{
char ch=st.top();
if((ch=='(' && s[i]==')') || (ch=='{' && s[i]=='}') || (ch=='[' && s[i]==']'))
{
st.pop();
}
else break;
}
else {d=1; break;} //there is nothing left in stack to compare with.
}
}
if(!d && st.empty()) pf("Yes\n");
else
{
pf("No\n");
while(!st.empty()) st.pop();
}
}
return 0;
}
view raw UVA 673 - Parentheses Balance.cpp hosted with ❤ by GitHub

Insertion sort

Arunima Mandal Leave a comment

Soluton: 

#include <bits/stdc++.h>
using namespace std;
int main()
{
int i,j,t,n,temp;
cout<<"Enter the array size : "<<endl;
cin>>n;
int a[n];
cout<<"The unsorted array elements are: "<<endl;
for(i=0; i<n; i++) cin>>a[i];
for(i=1; i<n; i++)
{
for(j=i; j>0; j--)
{
if(a[j]<a[j-1])
{
swap(a[j],a[j-1]);
}
else break;
}
}
cout<<"The sorted array is :"<<endl;
for(i=0; i<n; i++)
{
cout<<a[i]<<endl;
}
return 0;
}
view raw Insertion sort.cpp hosted with ❤ by GitHub

Bubble sort

Arunima Mandal Leave a comment

Solution:

#include <iostream>
using namespace std;
int main()
{
int i,j;
int n,temp; // In case of dealing with 'char', instead of 'int', 'char' would have to be written
cin>>n;
int a[n];
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(i=0;i<n;i++) cout<<a[i]<<endl;
return 0;
}
view raw Bubble sort.cpp hosted with ❤ by GitHub