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");
    }
}