UVA 10679 - I Love Strings!!

Problem Explanation

Category: Easy
Type: String Ad Hoc


This is simple string ad hoc problem. You just need to find out a substring of a given string. But the tricky situation is you have to find out a string which will match from the start of the given string.
Suppose you have a string  IamAgoodStudendAndILikeProgramming and your query string is mming . This is a substring string but in case of this problem this is not a solution. If your query string is IamAgoodS then it is a solution of the problem. That is your query string must have to match from the beginning of the main string.

For cource code link click here

Codeforces 946 A Partition

Explanation

category : Easy

You just need to sum up all numbers. If you find any negative number just make it positive.

Source code link

Codeforces 950 A Left-handers, Right-handers and Ambidexters

Problem Explanation

Category: Easy

One have to find out maximum number of player which is even. Check the amount of left hand player  right hand player. If the amount is not same then take a amount of player from ambidexters, which can make equal number for both left hand and right hand. after taking some player from ambidexters , if still there are some player remains in ambidexters then divide the player among left hand and right hand players. 

If the amount of ambidexters player is zero the just squre the value which is minimum of left hand and right hand players. 

Some test case

10 12 10

28

1 0 1

2

2 4 0

4

3 6 9

18

5 5 5

14

Source code link Click here

Find out divisors of a number with a efficient way

Suppose you have 24 and you need to find out all divisors of the number. The normally what we do? We just divide the number from 1 to 24. That is we have to check 24 times. For 24 it is not a problem. But if I ask you do the same operation for 1234567 or for 1000000 or for 2345678? 😛
The whole day will be spent, isn't it?
Now let's check one thing.
All divisor of 24 is 1,2,3,4,6,8,12,24 and
(1*24) = (2*12) = (3*8) = (4*6) = 24
Here we multiply first element with last element, second element with second last element and third element with third last element.
That is we need to multiply ith element and (n-1+i)th element and need to count total number of multiplication and then again multiply the total by 2.

But now the question is we are only given a number not the divisor list. Then what we should do? Yes, we will find out the list and just count with the above approach.
That is at first we divide

24 by 1 and we get 24 and the pair is (1,24)
24 by 2 and we get 12 and the pair is (2,12)
24 by 3 and we get 8 and the pair is (3,8)
24 by 4 and we get 6 and the pair is (4,6)
24 by 5 but this is not a divisor
24 by 6 and we get 4 and the pair is (4,6). We already got the pair so avoid it.
24 by 7 but this is not a divisor
24 by 8 and we get 3 and the pair is (3,8). We already got the pair so avoid it.

if we go more towards then same pair will appear that's why we will now stop. Now count how many time we did this. It is 8 times, isn't it? Carefully observe , if we stop our calculation at 5 or just before 6 that is when we get any pair which already occurred, we will be done. Carefully observe 5 is equal to integer part of (square root of 24 ) +1

Now lets take a look on the sudo code

1. Take a number n
2. For i=1 to (square-root of n) +1
3.  check if n is dividable by i or not
4. if dividable then count = count +1
5. if not go to 2 again
6. print value of count

You can check for 48,100,3000,4000. 

Now you have a home work. Follow bellow what I write

24 / 2 = 12

12 / 2 = 6

6 / 2 = 3

3 / 3 = 1

Upto 1 I get 4 result and now multiply 4*2 = 8. 

O My god!

Am I correct for the above calculation? Check yourself for 48, 100, 122 

If I correct then find out the sudo code or algorithm. 

UVA 11876 - N + NOD (N) (Explanation)

Problem Explanation

Problem Category : Medium
Algorithm: Binary Search, Mathematical Simulation

For this problem, if you know how to find out total divisor of a number in a efficient way, then your job 85% is done. For this problem at first I have found out all divisor of a number and added with that number.
That is if the number is x then x = x + divisor(x)
and also marked those x's by using an array and also found out total number of numbers in the sequence for the range 1 to 1000000. In a test case I just calculate the difference between the ranges.

If you want to use binary search algorithm the you need not sum up the array. For using binary search algorithm just store all x's in a array and run a loop from a to b and search the value and count.

One important thing. If you use array to mark the x's then you can declare the array in the main function or globally. But don't forget to set 0 to all indices of the array if you declare the array in the main function. If you declare the array globally then you need not set 0 to all indices. Now it's your choice what should to do for less time complexity 

For source code Click

UVA 11057 - Exact Sum (Explanation)

Problem Explanation

Problem Category: Easy
Algorithm : Binary search

Explanation: You are given a list of numbers which represent money and total money that the boy get. Take one element from the list and find out other element by subtracting from total amount of money. Use binary search for searching the another element after subtracting. When you will find the two number you have to check if their difference is minimum.
You can do the same operation by using loop but in worst case you will get time complexity. 

Don't forget to sort the data 😜

Sudo code:

1. Take one element from the list. This one should be  a
2.  now b = total  - a where total is the money which the boy was given in two weeks
3. check if a is greater than b, that mean this a already have checked, if it is true just break
4. if not the search b using binary search
5. When you will found check if b-a is minimum
6.  if b-a is minimum then store it as lowa and lowb.
7. Remember, your answer actually lowa and lowb

Check some test case:
8
12 9 3 15 18 5 10 6
21
8
12 9 3 15 18 5 10 6
15
8
12 9 3 15 18 5 10 6
33

If you face trouble you can see the code. Just Click

UVA 10474 - Where is the Marble? (Explanation)

Problem Explanation 
After reading the problem what do you think? Is it a problem of linear searching or anything else? Yes you can solve it by one for loop or linear search. But I think this is not a good solution.
Good approach is using binary search algorithm.
The important information I found from the description is " She would count 1...2...3" that is Meena always count from the start.
So suppose you have 5 numbers like 5 5 5 5 5 then Meena will count the first one. So if you just implement the binary search algorithm then also it will not work. You have to ensure that if there are same number in the list. And to do this just decrees the value of end index of the algorithm.
Don't forget to sort data😜
Here is the sudo code

begin =0
end = array_size-1
while begin<=end
if key_alue and mid value are same then
index = data[mid] and end = mid-1
or if key_value is greater than mid value then
begin = mid+1
or if key_value is smaller  then mid value then
end = mid-1

If you need to see the code then just  click 

UVA 10226 - Hardwood Species

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647


int main()
{
    int test,total,d;
    char str[40];
    map<string,int>my_map;
    map<string,int>::iterator it;
    vector<string>data;

    sc("%d\n\n",&test);
    while(test--)
    {
        total=0;
        while(gets(str))
        {
            if(strlen(str)==0)
                break;
            if(my_map.count(string(str))==0)
            {
                data.pb(string(str));
            }
            my_map[string(str)]++;
            total++;
        }
        sort(data.begin(), data.end());
        for(int i=0 ; i<data.size() ; i++)
        {
            d = my_map[data[i]];
            double value = (double)d / (double) total * 100.0 ;
            cout<<data[i]<<" ";
            pf("%.4lf\n",value);
        }
        my_map.clear();
        data.clear();
        if(test)
            pf("\n");
    }
}

UVA 10295 - Hay Points

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int m,n,k,sum;
    map<string,int>my_map;
    string str,word;


    sc("%d %d",&m,&n);
    while(m--)
    {
       cin>>str>>k;
       my_map[str]=k;
    }

    while(n--)
    {
        word = "";
        sum=0;
        while(true)
        {
            cin>>str;
            if(str[0]=='.' && str.size()==1)
            {
                pf("%d\n",sum);
                word = "";
                break;
            }
            for(int i=0 ; i<str.size() ; i++)
            {
                if(str[i]==' ')
                {
                    word = "";
                    continue;
                }
                word += str[i];
                if(str[i+1]==' ' || i==str.size()-1)
                {
                    if(my_map[word])
                    {
                        //cout<<word<<" ";
                        sum += my_map[word];
                    }
                    if(i==str.size()-1)
                        word = "";

                }
            }
        }
    }
    return 0;
}

UVA 11496 - Musical Loop

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int n,cnt,k;
    int data[10010];
    bool up, down;
    while(sc("%d",&n) &&n)
    {
       for(int i=0 ; i<n ; i++)
        sc("%d",&data[i]);

       up = down = false;
       if(data[n-1]<data[0])
        up = true;
       else
        down = true;
       data[n] = data[0];
       cnt=0;

       for(int i=1 ; i<=n ; i++)
       {
           if(data[i-1]<data[i] && down)
           {
               cnt++;
               down = false;
               up = true;
           }
           else if(data[i-1]>data[i] && up)
           {
               cnt++;
               up = false;
               down = true;
           }
       }

        pf("%d\n",cnt);
    }
    return 0;
}

UVA 11222 - Only I did it!

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int test,p,n,cs=1,big,frnd;
    int data[10010],cntuser[5];
    sc("%d",&test);
    while(test--)
    {
        memset(data,0,sizeof(data));
        int mx=0,mn=120000;
        memset(cntuser,0,sizeof(cntuser));

        for(int i=1 ; i<=3; i++)
        {
            sc("%d",&n);
            for(int j=1 ; j<=n ; j++)
            {
                sc("%d",&p);
                if(mx<p)
                    mx=p;
                if(mn>p)
                    mn=p;
                if(data[p] || data[p]==-1)
                {
                    data[p]=-1;
                    continue;
                }
                else
                {
                    data[p] =i;
                }
            }
        }

        for(int i=mn ; i<=mx ; i++)
        {
            if(data[i]==1 || data[i]==2 || data[i]==3)
            {
                if(data[i]==1) cntuser[1]++;
                else if(data[i]==2) cntuser[2]++;
                else cntuser[3]++;
            }
        }
        if(cntuser[1]>=cntuser[2])
        {
            big = cntuser[1];
        }
        else
        {
            big = cntuser[2];
        }

        if(big>=cntuser[3])
        {
            big = big;
        }
        else
        {
            big = cntuser[3];
        }
        pf("Case #%d:\n",cs++);

        for(int i=1 ; i<=3 ; i++)
        {
            if(cntuser[i]==big)
            {
                pf("%d %d",i,big);
                for(int j=mn ; j<=mx ; j++)
                {
                    if(data[j]==i)
                        pf(" %d",j);
                }
                pf("\n");
            }
        }


    }

    return 0;
}

UVA 10050 - Hartals

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int test,n,p,h;
    int data[3655];

    sc("%d",&test);
    while(test--)
    {
      sc("%d",&n);
      memset(data,0,sizeof(data));
      for(int i=6 ; i<=n ; i+=7){
        data[i]=-1;
        data[i+1]=-1;
      }
      sc("%d",&p);
      int cnt=0;
      for(int i=1 ; i<=p ; i++)
      {
          sc("%d",&h);
          for(int j=h ; j<=n; j+=h)
          {
            if(data[j]<0 || data[j])
                continue;
            else if(data[j]==0)
            {
                data[j]=1;
                cnt++;
            }
          }
      }
      pf("%d\n",cnt);

    }

    return 0;
}

UVA 11093 - Just Finish it up

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647


int main()
{
    int test, n,p,x;
    int petrol[200040];

    sc("%d",&test);
    int cs=1;
    while(test--)
    {
        sc("%d",&n);
        for(int i=1 ; i<=n ; i++)
        {
            sc("%d",&petrol[i]);
            petrol[n+i] = petrol[i];
        }

        for(int i=1 ; i<=n ; i++)
        {
            sc("%d",&x);
            petrol[i] -= x;
            petrol[n+i] -= x;
        }

        petrol[0] =0;
        for(int i=1 ; i<=2*n ; i++)
        {
            petrol[i] += petrol[i-1];
        }
        int s=0, mi=1,cnt=0;
        for(int i=0 ; i<=2*n ; i++)
        {
            if(petrol[i]>=mi)
            {
               if(++cnt>n)
                    break;
            }
            else
            {
                mi = petrol[i];
                s= i;
                cnt=1 ;
                if(i>=n)
                    break;
            }
        }
        if(cnt>n)
            pf("Case %d: Possible from station %d\n",cs++,s+1);
        else
            pf("Case %d: Not possible\n",cs++);
    }
}

UVA 10042 - Smith Numbers

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

vector<int>primeFactor ;

int sumOfNumberDigit(int n)
{
    //pf("#receive %d\n",n);
    int sum =0 ;
    while(1)
    {
        if(n==0)
            break;
        sum += n%10;
        //pf("%d ",n%10);
        n = n/10;
    }
    //pf("\n");
    return sum;
}

void findPrimeFactor(int n)
{
    while (n%2 == 0)
    {
        //pf("2 ");
        primeFactor.pb(2);
        n = n/2;
    }

    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
             //pf("%d ",i);
            primeFactor.pb(i);
            n = n/i;
        }
    }

    if (n > 2){
         //pf("%d ",n);
          primeFactor.pb(n);
    }

}

int main()
{
    int test,n,sum_num,sum;
    sc("%d",&test);
    while(test--)
    {
        sc("%d",&n);
        for(int i=n+1 ;  ; i++)
        {
            //pf("New one %d\n",i);
            sum_num = sumOfNumberDigit(i);
            //pf("%d sum_num: %d\n",i,sum_num);
            findPrimeFactor(i);
            sum=0;
            //pf("\n");
            if(primeFactor.size()==1)
            {
                primeFactor.clear();
                continue;
            }
            for(int j=0 ; j<primeFactor.size() ; j++)
            {
                sum += sumOfNumberDigit(primeFactor[j]);
            }
            //pf("%d %d\n",sum,i);
            if(sum == sum_num)
            {
                pf("%d\n",i);
                primeFactor.clear();
                break;
            }
            primeFactor.clear();
        }


    }

    return 0;
}

UVA 541 - Error Correction

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int n,x,y,num,row_odd,col_odd,r,c;
    int data[105][105],row[105],col[105];
    memset(row,0,sizeof(row));
    memset(col,0,sizeof(col));

    while(sc("%d",&n) &&n)
    {
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));

      for(int i=0 ; i<n ; i++)
        for(int j=0 ; j<n ; j++)
        {
          sc("%d",&data[i][j]);
          row[i] = row[i]+data[i][j];
          col[j] = col[j] + data[i][j];
        }
        row_odd = col_odd = 0;
        for(int i=0 ; i<n ; i++)
        {
            if(row[i]%2)
                row_odd++;
            if(col[i]%2)
                col_odd++;
           for(int j=0 ; j<n ; j++)
            if(row[i]%2 && col[j]%2)
            {
               r=i+1;
               c = j+1;
            }

        }
        if(row_odd>1 || col_odd>1)
            pf("Corrupt\n");
        else if(row_odd==0 && col_odd ==0)
            pf("OK\n");
        else if(row_odd==1 && col_odd==1)
            pf("Change bit (%d,%d)\n",r,c);

    }

    return 0;
}

Codeforces 939 A Love Triangle

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647

int main()
{
    int n;
    int data[5010];
    sc("%d",&n);
    for(int i=0 ; i<n ; i++)
        sc("%d",&data[i+1]);
    bool notGet = false ;
    for(int i=1 ; i<n+1 ; i++)
    {
        if( i == data[data[data[i]]])
        {
            pf("YES");
            notGet = true;
            break;
        }
    }
    if(notGet == false)
        pf("NO");

    return 0;
}

Codeforces 940 A Points on the line

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647

int main()
{
    int n,d,p;
    vector<int>data;
    int ans=-1;

    sc("%d %d",&n,&d);
    for(int i=1 ; i<=n ; i++)
    {
        sc("%d",&p);
        data.pb(p);
    }
    sort(data.begin(),data.end());

    for(int i=0;i<n;i++)for(int j=i;data[j]-data[i]<=d&&j<n;j++)
if(j-i+1>ans)ans=j-i+1;
    pf("%d",n-ans);
    return 0;
}