Kth smallest number in an array

Hi guys, in this post  i ‘ll tell you one more problem based on Divide and conquer approach. The earlier one was the matrix multiplication. So, the problem is about finding the kth_smallest element in an array of distinct elements. The approach will be familiar to the programmers who have done quick sort , as things are quit same.

Algorithm:-

First we will choose any element ‘a’ in the array and then we will partition the whole array into two sets such that one set contains elements less than ‘a’, while the other one contains greater than ‘a’. This is the same as we do in quicksort. Now we know the number of elements upto the pivot ‘a’. if this number is j then,

If j is equal to k, then ‘a’ will be the kth element. Otherwise, there will be two cases:

  1. If j<k, then the problem is changed into the subproblem of finding the (k-j)th element in the second partition i.e. set of elements greater than ‘a’.
  2. If j>k,  then the problem is changed into the subproblem of finding the kth element in the first partition i.e. set of elements less than ‘a’.

Now, the base case can be, if number of elements is equal to 1 , then return the only element.

Following is the recursive C++ code for finding the kth element in an array of n distinct elements:-

/*Program created by Shantanu Tripathi(SHAAN)
IPG_2014079
ABV-IIITM,Gwalior */
#include<bits/stdc++.h>
using namespace std;
#define _ ios::sync_with_stdio(false); cin.tie(0);
#define T() int t; cin>>t; while(t–)
#define f0(i,n) for(int i=0;i<n;i++)
#define f1(i,n) for(int i=1;i<=n;i++)
#define fk(i,k,n) for(int i=k;i<=n;i++)
#define fr(i,r,n) for(int i=r;i>=n;i–)
#define ll long long
#define l long
#define ri(n) int n; cin>>n;
#define ri2(x,y) int x,y; cin>>x>>y;
#define ri3(x,y,z) int x,y,z; cin>>x>>y>>z;
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define max3(a,b,c) ((max(a,b)>(c))?max(a,b):c)
#define min3(a,b,c) ((min(a,b)<(c))?min(a,b):c)

typedef vector<int> vi;
typedef vector<l> vl;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi > matrix;
typedef pair<int ,int> pi;
typedef pair<l,l> pl;
typedef pair<ll,ll> pll;
typedef vector<pi > vpi;
typedef vector<pll > vpll;
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define apresent(c,x) (find(all(c),x) != (c).end())
#define F first
#define S second
inline bool ispalindrome(string s) { for(int i=0,j=s.size()-1;i<=j;i++,j–) if(s[i]!=s[j]) return false; return true; }
inline bool ispalindrome(vi s) { for(int i=0,j=s.size()-1;i<=j;i++,j–) if(s[i]!=s[j]) return false; return true; }
#define ispalin(x) ispalindrome(x)
#define MOD 1000000007
inline ll gcd(ll a,ll b) { return ((b==0)?a:gcd(b,a%b)); }
inline ll modexp(ll a,ll b,ll m) { ll d=1; while(b>0) { if(b&1) d=(d*a)%m; a=(a*a)%m; b=b>>1; } return (d<0?d+m:d); }
inline bool isPrime(ll x) { for(ll a = 2; a * a <= x; ++a) if(x % a == 0) return false; return true; }
inline ll powf(ll a,ll b) { ll d=1; while(b>0) { if(b&1) d=d*a; a=(a*a); b=b>>1; } return d;}
ll ncr(l n ,l r){vector<vl > dp(2,vl(r+1,0)); f1(i,n) fk(j,0,min(i,r)) dp[i&1][j] = ((i==j || j==0)?1:(dp[(i-1)&1][j] + dp[(i-1)&1][j-1])%MOD); return dp[n&1][r]; }
ll ncr2(l n, l r) { ll ans=1; for(l i = n;i>r;i–) ans = (ans*i)%MOD; f1(i,n-r) ans = (ans*(modexp(i,MOD-2,MOD)))%MOD; return ans; }
ll phi(ll n){ ll ret=n; ll i = 2; if(n%i==0){ ret-=ret/i; while(n%i==0)n/=i;} for(i=3; i*i<=n; i++)if(n%i==0){ ret-=ret/i; while(n%i==0)n/=i;} if(n>1)ret-=ret/n;return ret;}
#define MAX 1000007
/*
int sq = sqrt(MAX);
vb isprime(MAX+1,1);
vi small(MAX+1);
void sieve() { isprime[0]=isprime[1]=0; int i,j; for(i=4;i<=MAX;i+=2) isprime[i]=0;for(i=3;i<=sq;i+=2) if(isprime[i]) for(j=i*i;j<=MAX;j+=(i+i)) isprime[j]=0; }
void smallprime(){int i,j; small[0]=small[1]=0;for(i=2;i<=MAX;i++) small[i]=(i&1)?i:2;for(i=3;i<=sq;i+=2) if(small[i]==i) for(j=2*i;j<=MAX;j+=i) if(small[j]==j) small[j]=i;}
void fact(ll n){ll temp=small[n],prod=1,count=0;while(n>1) {if(temp==small[n])count++;else{cout<<temp<<“^”<<count<<” “;prod*=(count+1);temp=small[n];count=1;}n/=small[n];}cout<<temp<<“^”<<count<<” “<<endl;prod*=(count+1);}
ll phi2(ll n){if(n==1)return 1; ll temp=small[n], count=n; while(n>1){if(temp!=small[n]){ count -= count/temp; temp = small[n];} n /= small[n]; }count -= count/temp; return count;}
*/
void swap(int *a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int a[],int start, int end)
{
int mid = (start + end)/2;
int pivot = a[mid]; // taking middle element as pivot
int i = start;
swap(&a[mid],&a[end]); // repalcing with the last element
fk(j,start,end-1)
{
if(a[j] < pivot)
{
if(i!=j)
swap(&a[i],&a[j]);
i++;
}
}
if(i!=end)
swap(&a[i],&a[end]);
return i; // correct position of the pivot if elemnts were sorted from start to end
}
int kth_smallest(int a[], int k, int start, int end)
{
if(start == end)
return a[start];
int p = partition(a,start,end);
if((p – start + 1) == k) // if elements were sorted from start to end then then (p – start + 1)th element is a[p]
return a[p];
else if((p – start + 1) < k)
return kth_smallest(a,k -(p – start + 1), p + 1,end);
else return kth_smallest(a,k,start,p-1);
}
int main()
{
_
ri(n)
int a[n];
f0(i,n) cin>>a[i];
ri(k)
cout<<kth_smallest(a,k,0,n-1)<<endl;
return 0;
}

Please leave comments in case of anny doubt!- shAAn

Advertisements

Strassen’s matrix multiplication algorithm

probably you have known the naive matrix multiplication of two matrices taking time of the order of n^3 where n is the size of the matrix. Here is the quick view of the Strassen algorithm which works better than the naive method for higher inputs .

ALGORITHM:-

Suppose u have to do the following matrix multiplication:-

X = Y.Z         (n x n) size

Divide X , Y, Z each into 4 (n/2) x(n/2) matrices
Then,
I = AE + BG
J = AF + BH
K = CE + DG
L = CF + DH

where I,J,K,L are the submatrices of the resulting matrix X, A,B,C,D  are the submatrices of the matrix Y , E,F,G,H  are the submatrices of the matrix Z.

Then Compute:
M1:=(A+C)(E+F)
M2:=(B+D)(G+H)
M3:=(A-D)(E+H)
M4:=A(F-H)
M5:=(C+D)E
M6:=(A+B)H

M7 := D(G-E)

Here, M1,M2,M3,M4,M5,M6 and M7 are the temporary matrices of the size n/2 x n/2.

Then,
I:=M2+ M3–M6–M7
J:=M4+ M6
K:=M5+ M7
L:=M1–M3 –M4–M5
now , conbine all the 4 submatrices into the single resulting matrix X.

Following is the C++ code implementing the above algorithm:-

// Shantanu Tripathi, IPG_2014079, ABV-IIITM
#include<bits/stdc++.h>
using namespace std;
typedef vector<vector<long long> > matrix;
#define LIMIT 10
class matrixmul
{
public:
matrix X,Y;
matrixmul(int n) // constructor
{
X.resize(n);
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
{
long long x = rand()%LIMIT;
X[i].push_back(x);
}
Y.resize(n);
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
{
long long x = rand()%LIMIT;
Y[i].push_back(x);
}
}
matrix addmatrix(matrix a, matrix b, int size) // addition method for two matrices a and b of size x size
{
matrix temp(size);
for(int i = 0;i<size;i++)
for(int j = 0;j<size;j++)
temp[i].push_back(a[i][j] + b[i][j]);
return temp;
}
matrix submatrix(matrix a, matrix b, int size) // subtraction method for two matrices a and b of size x size
{
matrix temp(size);
for(int i = 0;i<size;i++)
for(int j = 0;j<size;j++)
temp[i].push_back(a[i][j] – b[i][j]);
return temp;
}
void printmatrix(matrix a, int size) // print method to print any matrix a of size x size
{
for(int i = 0;i<size;i++)
{
for(int j = 0;j<size;j++)
cout<<a[i][j]<<” “;
cout<<endl;
}
}
matrix mul(matrix x, matrix y, int n) // recursive method for the multiplication of two matrices x and y of size n x n
{
matrix z(n); // resulting matrix z
if(n == 1) // base case
{
z[0].push_back(x[0][0]*y[0][0]);
return z;
}
int size = n/2;
matrix a(size),b(size),c(size),d(size),e(size),f(size),g(size),h(size);
// partition matrix x into 4 matrices of size x size i.e n/2 x n/2
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
{
if(i<size && j<size)
a[i].push_back(x[i][j]);
else if(i<size && j>=size)
b[i].push_back(x[i][j]);
else if(i>=size && j<size)
c[i – size].push_back(x[i][j]);
else d[i – size].push_back(x[i][j]);
}
// partition matrix y into 4 matrices of size x size i.e n/2 x n/2
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
{
if(i<size && j<size)
e[i].push_back(y[i][j]);
else if(i<size && j>=size)
f[i].push_back(y[i][j]);
else if(i>=size && j<size)
g[i – size].push_back(y[i][j]);
else h[i – size].push_back(y[i][j]);
}
// 7 intermediate matrices required of size ” size x size”
matrix m1(size),m2(size),m3(size),m4(size),m5(size),m6(size),m7(size);
m1 = mul(addmatrix(a,c,size),addmatrix(e,f,size),size);
m2 = mul(addmatrix(b,d,size),addmatrix(g,h,size),size);
m3 = mul(submatrix(a,d,size),addmatrix(e,h,size),size);
m4 = mul(a, submatrix(f,h,size),size);
m5 = mul(addmatrix(c,d,size),e,size);
m6 = mul(addmatrix(a,b,size),h,size);
m7 = mul(d, submatrix(g,e,size),size);
matrix I(size), J(size), K(size), L(size); // partitions of the resulting matrix z of size n/2 x n/2
// recurrence for each matrix partiton of the resulting matrix i.e. I,J,K and L
I = submatrix(addmatrix(m2,m3,size), addmatrix(m6,m7,size), size);
J = addmatrix(m4,m6,size);
K = addmatrix(m5,m7,size);
L = submatrix(m1, addmatrix(addmatrix(m3,m4,size),m5,size), size);
// combining all the partitons into the resulting matrix z
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
{
if(i<size && j<size)
z[i].push_back(I[i][j]);
else if(i<size && j>=size)
z[i].push_back(J[i][j – size]);
else if(i>=size && j<size)
z[i].push_back(K[i – size][j]);
else z[i].push_back(L[i – size][j – size]);
}
return z;
}
};

int main()
{
int n = 256; // size of the matrix : n x n
matrixmul t(n); // construction of the matrixmul object
cout<<“First matrix is: “<<endl;
t.printmatrix(t.X,n);
cout<<endl;
cout<<“Second matrix is: “<<endl;
t.printmatrix(t.Y,n);
cout<<endl;
/* cout<<“Addition of two matrices is: “<<endl;
t.printmatrix(t.addmatrix(t.X,t.Y,n), n);
cout<<endl;
cout<<“Subtration of the two matrices is: “<<endl;
t.printmatrix(t.submatrix(t.X,t.Y,n),n);
cout<<endl; */
cout<<“Program is still running…. just wait for sometime\nProduct of the above two matrices is:”<<endl;
clock_t start,end;
start = clock();
t.printmatrix(t.mul(t.X,t.Y,n), n);
end = clock();
cout<<endl;
cout<<“Time taken by dev-c++ 5.11 c++ IDE in execution is: “<<((double)end – (double)start)/CLOCKS_PER_SEC<<” seconds;
return 0;
}

You can the change the size of the matrix by changing the value of n in the main().

Note:- this will work only for n which is a power of 2. Now, you implement the algorithm for the general value of n.

Binary Indexed tree

Binary indexed tree (or Fenwick tree) is a data structure which helps to convert an array representation in a form such that the calculation of some f(x) for a prefix of some given array can be done in logarithmic time. The f(x) can be any function for which its inverse is possible, such as

  1. Addition has inverse subtraction
  2. Multiplication has inverse division
  3. Sum of matrices has inverse, etc.

For example , we have been given an array arr[n] of n elements and you have two types of tasks or queries to complete like :-

a) Change the value stored at an index i. (This is called a point update operation)

b) Find the sum of a prefix of length k. (This is called a range sum query)

The brute force implementation will take time of he order of O(1) for the first query and O(n) for the second query . Through the BIT , we can do both the operations in O(logn) time with O(n) space complexity(for the BIT array to be discussed soon).

Concept behind Binary Indexed Tree

Before understanding the concept of BIT, you should learn about a bit manipulation trick ,i.e, Isolating the last set bit.

Isolating the last set bit:-

Suppose if x = a1b , where b= all 0’s and a is a set of 0’s and 1’s. That means 1 behind b is the last set bit and we have to isolate that one (in decimal). Let see what happens when we have AND ‘a1b’ with its 2’s complement ‘(~a) 1 (all 0s)’, i.e., a’1b.

06ae541

Hence , by performing the operation x &(~x) , we get the last set bit isolated.

Now let’s see why we need the concept of the last isolated bit. We will create an array BIT[n] which will store the partial sums of the given array at different indexes.Every index ‘i’ which is a power of 2 will store the prefix sum upto the index ‘i’, i.e., BIT[i]= arr[1] + arr[2] +…. arr[i]. In the same way every odd index in the BIT[] will store only the value at that index in arr[] .

For example,

BIT[1] = arr[1];

BIT[2] = arr[1] + arr[2];

BIT[3]= arr[3];

BIT[4] = arr[1] + arr[2] + arr[3] + arr[4];

In general , we can say that every index i in the BIT[] array stores the cumulative sum from the index i to i(1<<r)+(both inclusive), where r represents the last set bit in the index i.

i.e. (1<<r) = x & (~x) (last isolated set bit).

For example: BIT[6] = arr[5] + arr[6];

BIT[12] = arr[9] +arr[10] +arr[11] +arr[12];

Creation and Updating of Binary Indexed Tree

Initially the Binary indexed tree has zero at its every index . We will use update() to create BIT[] on the basis of the given arr[]. Suppose ,we have to add value equals to ‘val’ at the index ‘id’ in arr[], then we will have to update every index i in the BIT[], wherever the partial sum includes the arr[id]. For example , if we have to add 2 to the index 4 of the arr[] of 8 elelments(n=8), then BIT[4] as well as BIT[8] will have to be updated as both contains arr[4].

This thing can be done by incrementing the given index id by its last isolated bit until reaches the n, and updating each BIT[id].Below is the appropriate snippet for the update operation.

void update(int id, int val) // adds val to the index id

{

for(;id<=n;id += id&(-id))

BIT[id]+=val;

}

calculation of the prefix sum

For the calculation of the prefix sum, let us take the example of an arr[] of 12 elements and we have to calculate the prefix sum of first 12 elements. Since we know that BIT[12] contains the sum of the elements from arr[12] to arr[9]. Hence , we have to go to BIT[8] to retrieve the rest sum of the elements from arr[8] to arr[1]. And 8 = 12 -(1<<2), where 2th bit is the last set bit of 12.

generalizing it, we can find the prefix sum of index id, by decrementing the index id by the value of its last set bit until it becomes 0.Below is the code snippet for it.

void query(int id)

{

int sum = 0;

for(;id>0; id -= id&(-id))

{

sum+=BIT[id];

}

return sum;

}

Here is the full program that updates value at a given index and finds the prefix sum of any index in the arr[] of n elements;

int BIT[1000], arr[1000], n;
void update(int id, int val)
{
      for(; id <= n; id += id&-id)
        BIT[id] += val;
}
int query(int id)
{
     int sum = 0;
     for(; id > 0; id -= id&-id)
        sum += BIT[id];
     return sum;
}

int main()
{
     cin>>n;
     for(int i = 1; i <= n; i++)
     {
           scanf(“%d”, &a[i]);
           update(i, a[i]);
     }
    cout<<"sum of first 10 elements is "<< query(10);
    cout<<"sum of all elements in range [2, 7] is "<<query(7)  query(2-1);
     return 0;
}

Applications:
Used to implement the arithmetic coding algorithm. Actually first of all it was used in arithmetic coding algorithm for certain tasks. So, the way it was used inspires the logarithmic  operations  for which it is used in general purpose programming. It is also a good technique to count inversions in an array in 0(nlog(n)) time.It can be preferred over the segment trees as its space complexity is less than that of segment tree and also less coding is required. 🙂