UNIQUE CHAR IN STRING

Q.) FIND UNIQUE CHAR IN  A GIVEN STRING.

SOLUTION---

#include
#include
int main()
{
    char str[400];
    scanf("%s",str);
    int i,d,len;
    len=strlen(str);
    int arr[128];
    for(i=0;i<128;i++)
        arr[i]=0;
    for(i=0;i<len;i++)
    {
        d=str[i];
        arr[d]+=1;
    }
    for(i=0;i<len;i++)
    {
        d=str[i];
        if(arr[d]==1){
            printf("%c ->unique char in string",str[i]);
           
        }
    }
    return 0;
}

REMOVE THE DUPLICATES FROM STRING

Q.) REMOVE THE DUPLICATES FROM A STRING WITH O(N).

SOLUTION---

#include
#include
int main()
{
    char str[400];
    scanf("%s",str);
    int arr[128];
    int i,d,len;
    for(i=0;i<128;i++)
        arr[i]=0;
    len=strlen(str);
    for(i=0;i<len;i++)
    {
         d=str[i];
        arr[d]+=1;
    }
    for(i=0;i<len;i++)
    {
        d=str[i];
        if(arr[d]!=0)
        {
            printf("%c",str[i]);
            arr[d]=0;
        }
    }
    return 0;
}
 

if you have better solution post ur code with ur name in comment after that ur correct solution will updated on this blog with ur name.

SORT THE ARRAY CONTAINING ONLY 0's AND 1's

Q.) SORT THE ARRAY CONTAINING ONLY 0's AND 1's .

SOLUTION--

#include
void swap(int *x,int *y)
{
        int temp;
        temp=*x;
        *x=*y;
        *y=temp;
        //return 0;
}
int main()
{
        int num,i,j;
        scanf("%d",&num);
        int arr[num];
        for(i=0;i<num;i++)
                scanf("%d",&arr[i]);
        for(i=0,j=num-1;i<=j;)
        {
                if(arr[i]==0)
                        i++;
                else{
                if(arr[j]==0)
                        swap(&arr[i],&arr[j]);
                j--;
                }
        }
        for(i=0;i<num;i++)
                printf("%d ",arr[i]);
        return 0;
}

solution by chris clerville (java) --

import java.util.Arrays;

public class SortZerosAndOnes {

static int[] sortZerosAndOnes(int[] a) {
if (a.length < 2) {
return a;
}
int len = a.length;
int sum = 0;

for(int i = 0 ; i < len ; i++) {
if(a[i] == 1) {
sum += a[i]; // The result will be the number of 1s in the array
a[i] = 0; // Make all the 1s zeros
}
}

// In reverse order place the 1s back into the array
for(int i = 0 ; i < sum ; i++) {
a[a.length-i-1] = 1;
}

return a;
}

public static void main(String[] args) {
int[] a = {0,1,0,1,0,1,1,0,1,0,0};
System.out.println(Arrays.toString(sortZerosAndOnes(a)));
// OUTPUT: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
}
}

MAXIMUM AREA OF RECTANGLE IN HISTOGRAM

Question:

-------- 

Find the maximum rectangle (in terms of area) under a histogram in the most optimal way. This means to find the area of largest rectangle that can be extracted from the Histogram.

SOLUTION BY ARNAB DUTTA  :

------

------------------------------------Max Rectangle Finder Class---------------------------------
/*
 * @author arnab
 */
public class MaxRectangleInHistogram {
   
    Stack S;
    StackItem curr;
    StackItem maxRectangle;
   
    public StackItem getMaxRectangleInHistogram(int A[], int n){
        int i = 0;
        S = new Stack();       
        S.push(new StackItem(0,0,-1));
        maxRectangle = new StackItem(0,0,-1);
       
        while(i           
                curr = new StackItem(i,A[i],i);
               
                    if(curr.height > S.peek().height){
                            S.push(curr);
                    }else if(curr.height == S.peek().height){                           
                            S.peek().sup = i+1;                        
                    }else if(curr.height < S.peek().height){                           
                           
                            while((S.size()>1) && (curr.height<=S.peek().height)){
                                curr.sub = S.peek().sub;
                                S.peek().sup = i;
                                decideMaxRectangle(S.peek());
                                S.pop();
                            }                              
                        S.push(curr);                   
                    }
            i++;
        }
       
        while(S.size()>1){
            S.peek().sup = i;
            decideMaxRectangle(S.peek());
            S.pop();           
        } 
           
        return maxRectangle;
    }
   
    private void decideMaxRectangle(StackItem s){
       
        if(s.getArea() > maxRectangle.getArea() )
            maxRectangle = s;     
    }
   
}
------------------------------------Abstract Data Type Class---------------------------------

/*
 * @author arnab
 */
public class StackItem{
    public int sup;
    public int height;
    public int sub;
   
    public StackItem(int a, int b, int c){
        sup = a;
        height = b;
        sub =c;
       
    }   
   
   public int getArea(){
        return (sup - sub)* height;
   }
  
    @Override
   public String toString(){
       return "     from:"+sup+
              "     to:"+sub+
              "     height:"+height+             
              "     Area ="+getArea();
   }
}
----------------------------------------Test Class---------------------------------/*
 * @author arnab
 */ 
public class MyTestClass {
   
    public static void main(String args[]){  
         MaxRectangleInHistogram maxRectInHist = new MaxRectangleInHistogram();
        int[] heights = {3,2,5,6,1,4,4};
        int n = heights.length;
        StackItem maxRectangle = maxRectInHist.getMaxRectangleInHistogram(heights, n);
        System.out.println("The Continuous Maximum Recatngle in the Histogram is :- \n"+maxRectangle);
    }
   
}

Explanation:

-----------

Please download the PDF from

http://www.scribd.com/doc/112600829/Rectangle-of-Max-AREA-in-Histogram

Find a pair of elements from an array whose sum equals a given number

Q.) Find a pair of elements from an array whose sum equals a given number (a,b)

source code:

#include
#include
using namespace std;
int main()
{
    int num, X,i,ub,lb,search_num,mid,flag;
    printf("enter the size of array=");
    scanf("%d",&num);
    scanf("%d",&X);
    int arr[num];
    for(i=0;i<num;i++)
        scanf("%d",&arr[i]);
    sort(arr,arr+num);
    for(i=0;i<num;i++)
    {
        //binary search of search_num//
        search_num=X-arr[i];
        lb=0,ub=num-1,flag=0;
        if(search_num>0)
        {
            while(lb<=ub)
            {
                mid=(lb+ub)/2;
                if(arr[mid]==search_num)
                {
                    flag=1;
                    break;
                }
                else if(arr[mid]>search_num)
                    ub=mid-1;
                else
                    lb=mid+1;
            }
        }
        if(flag==1&&mid!=i){
            printf("(%d,%d)\n",arr[i],arr[mid]);
           num=num-1; //decreasig the size of the array to stop reapeating ans like (1,11) (11,1)//
        }
    }
    return 0;
}

atoi function

Q.) Implemnet atoi function (amazon interview question)

source code:

#include
 
 
int atoi(char s[])
{
    int i,n;
    n=0;
    for(i=0;s[i]>='0'&&s[i]<='9';++i)
        n=10*n+(s[i]-'0');
    return n;
}
int main()
{
    char s[100];
    scanf("%s",s);
    int num=atoi(s);
    printf("%d",num);
    return 0;
}

TRAVERSING GRID

SPOJ Problem Set (classical)

5976. Traversing Grid

Problem code: TRGRID

Starting at the top left corner of an N*M grid and facing towards the right, you keep walking one square at a time in the direction you are facing. If you reach the boundary of the grid or if the next square you are about to visit has already been visited, you turn right. You stop when all the squares in the grid have been visited. What direction will you be facing when you stop ?

For example : Consider the case with N = 3,M = 3. The path followed will be (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) -> (2,0) -> (1,0) -> (1,1). At this point, all squares have been visited, and you are facing right.


Input


The first line contains T the number of test cases. Each of the next T lines contain two integers N and M, denoting the number of rows and columns respectively.



Output

Output T lines, one for each test case, containing the required direction you will be facing at the end. Output L for left, R for right, U for up, and D for down.

Eample


Sample Input :
4
1 1
2 2
3 1
3 3

Sample Output :
R
L
D
R

SOLUTION---

#include
int main()
{
    long long int n,m;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&n,&m);
        if(n%2==0&&m%2==0)
        {
            if(n>m)
                printf("U\n");
            else if(m>=n)
                    printf("L\n");
        }
        else if(n%2!=0&&m%2!=0)
        {
            if(n>m)
                printf("D\n");
            else if(m>=n)
                printf("R\n");
        }
        else
        {
            if(n%2==0&&m%2!=0)
                {
                    if(n>m)
                        printf("D\n");
                    else
                        printf("L\n");
                }
            if(n%2!=0&&m%2==0)
                {
                    if(n<m)
                        printf("R\n");
                    else
                        printf("U\n");
                }
        }
    }
    return 0;
}