The Mirror of Galadriel

SPOJ Problem Set (classical)

13043. The Mirror of Galadriel

Problem code: AMR12D

With water from the stream Galadriel filled the basin to the brim, and breathed on it, and when the water was still again she spoke. 'Here is the Mirror of Galadriel,' she said. 'I have brought you here so that you may look in it, if you will. For this is what your folk would call magic, I believe; though I do not understand clearly what they mean; and they seem also to use the same word of the deceits of the Enemy. But this, if you will, is the magic of Galadriel. Did you not say that you wished to see Elf-magic?' - Galadriel to Frodo and Sam, describing her Mirror.

We call a string S magical if every substring of S appears in Galadriel's Mirror (under lateral inversion). In other words, a magical string is a string where every substring has its reverse in the string.

Given a string S, determine if it is magical or not.



Input (STDIN):

The first line contains T, the number of test cases. The next T lines contain a string each. 



Output (STDOUT):

For each test case, output "YES" if the string is magical, and "NO" otherwise.



Constraints:

1 <= T <= 100

1 <= |S| <= 10

S contains only lower-case characters.



Sample Input:

2

aba

ab



Sample Output:

YES

NO



Notes/Explanation of Sample Input:

For the first test case, the list of substrings are : a, b, ab, ba, aba. The reverse of each of these strings is present as a substring of S too.

For the second test case, the list of substring are : a, b, ab. The reverse of "ab", which is "ba" is not present as a substring of the string.

SOURCE CODE--

#include
#include
int main()
{
    int t,middle,len,end,i;
    char arr[1000001];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",arr);
        len=strlen(arr);
        if(len==1)
            printf("YES\n");
        else if(len==2)
        {
            if(arr[0]==arr[1])
                printf("YES\n");
            else
                printf("NO\n");
        }
        else
        {
            if(len%2==0)
            {
                middle=len/2-1;
                end=len-1;
                for(i=0;i<=middle;i++)
                {
                    if(arr[i]==arr[end])
                        end=end-1;
                    else{
                        printf("NO\n");
                        break;
                    }
                }
                if(i==middle+1)
                    printf("YES\n");
            }
            else
            {
                middle=len/2;
                end=len-1;
                for(i=0;i<middle;i++)
                {
                    if(arr[i]==arr[end])
                        end=end-1;
                    else
                    {
                        printf("NO\n");
                        break;
                    }
                }
                if(i==middle)
                    printf("YES\n");
            }
        }
    }
    return 0;
}
 
 
 

THE SOLUTION IS VERY EASY WE HAVE TO CHECK ONLY WHETHER THE STRING IS PELINDROME OR NOT :)

Resource:

ICPC Asia regionals, Amritapuri 2012

Onotole needs your help

SPOJ Problem Set (classical)

7742. Onotole needs your help

Problem code: OLOLO

Onotole has a lot of pyani. Each pyani has a number, writing on it. Pyanis with equal numbers are indistinguishable. Onotole knows everything, so, he knows that each pyani appeared twice, and only one pyani is unique. He wants to get вздръжни эффект, and he needs the unique pyani. Given the list of pyanis denote which one of them appeared once (it is guaranteed that other pyanis appeared twice).



Input

First line of input contains number of pyanis N<=500 000. Next N lines contain a single positive integer 1 <= Pi <= 10^9.

Output

Output one positive integer on pyani, which appeared once.

Example

Input:
3
1
8
1
Output:
8



SOLUTION--

ALL ELEMENTS IN THE ARRAY APPEAR TWICE IN THE LIST EXCEPT ONE.

SO THERE IS A EASY AND BEST SOLUTION WITH O(n) TIME AND O(1) SPACE.

USING X-ORing OF ALL THE ELEMENTS THEN THE FINAL ANSWER WILL SHOW THE UNIQUE ELEMENTS IN THE GIVEN LIST .

SOURCE CODE---

#include
int main()
{
    int n,i;
    scanf("%d",&n);
    long long int arr[n];
    for(i=0;i<n;i++)
        scanf("%lld",&arr[i]);
    long long int a,ans;
    a=arr[0];
    for(i=1;i<n;i++)
    {
        ans=a^arr[i];
        a=ans;
    }
    printf("%lld\n",ans);
    return 0;
}

/* HERE a is a variable having value at position zero and the then there is a variable which is equal to X-OR of element a and arr[i] and then we assign value of ans in variable a. 

if you find any bugs or more efficient solution than this than post in comments.

thnxx!!

The Indian Connection SPOJ

SPOJ Problem Set (classical)

11402. The Indian Connection

Problem code: DCEPC504

Rajesh Kuthrapali has a weird family structure. Every male member gives birth to a male child first and then a female child whereas every female member gives birth to a female child first and then to a male child. Rajesh analyses this pattern and wants to know what will be the Kth child in his Nth generation. Help him.

Note:

1.Every member has exactly 2 children.

2. The generation starts with a male member(Rajesh).

3. In the figure given below:

                                   M-------- 1st generation 

                              /        \
                          M             F ------- 2nd generation
                        /    \         /   \
                      M     F       F     M
                                      |
                                   3rd child of 3rd generation

Input

First line specifies T, the number of test cases.

Next T lines each gives 2 numbers, N and K

Output

Output 1 line for each test case giving the gender of the Kth child in in Nth generation.

Print “Male” for male “Female” for female (quotes only for clarification).

Constraints

1<=T<=100

1<=N<=10000

1<=K<=min(10^15 , 2^(n-1))

Example

Input:
4
1 1
2 1
2 2
4 5 
Output:
Male
Male
Female
Female

solution---


this question is related to THUE MORSE series.
sequence http://oeis.org/A010060

how to create THUE MORSE series--

a(2n)=a(n)
a(2n+1)=1-a(n)

let for n=0,a(0)=0;

n = 0, substituting in Eq. 1: t1 = 1 - t0 = 1 (t0 is 0)

n = 1, substituting in Eq. 2: t2 = t1 = 1

n = 1, substituting in Eq. 1: t3 = 1 - t2 = 1 - 1 = 0

n = 2, substituting in Eq. 2: t4 = t2 = 1

n = 2, substituting in Eq. 1: t5 = 1 - t4 = 1 - 1 = 0

n = 3, substituting in Eq. 2: t6 = t3 = 0

n = 3, substituting in Eq. 1: t7 = 1 - t6 = 1 - 0 = 1

HERE is the code

#include
int main()
{
    int t,count;
    long long int k,num;
    scanf("%d",&t);
    while(t--)
    {
        count=0;
        scanf("%lld %lld",&k,&num);
        if(num==1)
            printf("Male\n");
        else if(num==2)
            printf("Female\n");
        else{
            num=num-1;
        while(num>1)
        {
            if(num%2!=0)
                count+=1;
            num=num/2;
        }
        if(count%2==0)
            printf("Female\n");
        else
            printf("Male\n");
        }
        printf("\n");
    }
    return 0;
}
 

GOOGLE INTERVIEW QUESTION

GOOGLE INTERVIEW QUESTION 1(USA)

Q.) can you efficiently implement three stacks in a single array, such that no stack overflows until there is no space left in the entire array space.

SOLUTION--

METHOD:

1.  Make the first stack from position zero(arr[0]).

2.  Make the second stack using from last position (position=size of        array -1) .

3.  Now there is the problem how we can make second stack using one array . Lets take we start the stack2 from position= size of arr/2+1, now only we have to manage the stack2 according to the empty space  in array, such that move the stack2 forward with increasing its top2 position by 1 and bottom2 by 1 or move the stack backward with decreasing the top2 by 1 and bottom2 by 1. 

try it happy CODING ...

-----------------------------------------------------------------------------------------------------------

#include

#define MAX 20

int top1=-1,top2=MAX/2,top3=MAX,bottom2=MAX/2+1,flag=0;

int arr[MAX];

void arrange_stack2_forward()

{

    int i;

    for(i=top2;i>=bottom2;i--)

    {

        arr[i+1]=arr[i];

    }

    top2=top2+1;

    bottom2=bottom2+1;

}

void arrange_stack2_backward()

{

    int i;

    for(i=bottom2;i<=top2;i++)

    {

        arr[i-1]=arr[i];

    }

    bottom2=bottom2-1;

    top2=top2-1;

}

void push_stack1(int item)

{

    if(top1+1==bottom2&&top2==top3-1){

        printf("arey is full\n");

        flag=1;

    }

    else if(top1+1==bottom2&&top2!=top3-1){

        arrange_stack2_forward();

        top1=top1+1;

        arr[top1]=item;

    }

    else

    {

        top1=top1+1;

        arr[top1]=item;

    }

}

void pop_stack1()

{

    if(top1==-1)

    printf("stack1 is empty\n");

    else{

    int poped_item=arr[top1];

    top1=top1-1;

    printf("poped item=%d\n",poped_item);

    }

}

void display_stack1()

{

    int i;

    if(top1==-1)

    printf("stack1 is empty\n");

    else{

    printf("STACK1 DISPLAY\n");

    for(i=top1;i>=0;i--)

    {

        printf("%d ",arr[i]);

    }

    printf("\n");

    }

}

void push_stack2(int item)

{

    if(top2+1==top3&&bottom2==top1+1){

        printf("array is full\n");

        flag=1;

    }

    else if(top2+1==top3&&bottom2!=top1+1){

        arrange_stack2_backward();

        top2=top2+1;

        arr[top2]=item;

    }

    else{

        top2=top2+1;

        arr[top2]=item;

    }

}

void pop_stack2()

{

    if(bottom2==top2+1)

        printf("stack2 is empty\n");

    else{

    int poped_item=arr[top2];

    top2=top2-1;

    printf("poped item=%d\n",poped_item);

    }

}

void display_stack2()

{

    int i;

    if(bottom2==top2+1)

        printf("stack2 is empty\n");

    else{

    printf("DISPLAY STACK2\n");

    for(i=top2;i>=bottom2;i--)

    {

        printf("%d ",arr[i]);

        printf("\n");

    }

    }

}

void push_stack3(int item)

{

    printf("bottom2=%d,top2=%d\n",bottom2,top2);

    if(top3-1==top2&&bottom2==top1+1)

    {

        printf("array is full\n");

    }

    else if(top3-1==top2&&bottom2!=top1+1)

    {

        arrange_stack2_backward();

        top3=top3-1;

        arr[top3]=item;

    }

    else{

        top3=top3-1;

        arr[top3]=item;

    }

}

void pop_stack3()

{

    if(top3==MAX)

        printf("stack3 is empty\n");

    else{

    int poped_item=arr[top3];

    top3=top3+1;

    printf("poped item=%d\n",poped_item);

    }

}

void display_stack3()

{

    int i;

    if(top3==MAX)

        printf("stack3 is empty\n");

    else{

    printf("DISPLAY STACK3\n");

    for(i=MAX-1;i>=top3;i--)

        printf("%d ",arr[i]);

        printf("\n");

    }

}

int main()

{

    int item,choice,pop_item;

    printf("enter choice\n");

    printf("1. push on stack1\n");

    printf("2. pop on stack1\n");

    printf("3. display stack1\n");

    printf("4. push on stack2\n");

    printf("5. pop on stack2\n");

    printf("6. display stack2\n");

    printf("7. push on stack3\n");

    printf("8. pop on stack3\n");

    printf("9. display stack3\n");

    printf("10. QUIT\n");

    printf("enter choice=");

    scanf("%d",&choice);

    do

    {

        switch(choice)

        {

            case 1: printf("enter item=");

                    scanf("%d",&item);

                    push_stack1(item);

                    break;

            case 2: pop_stack1();

                    break;

            case 3: display_stack1();

                    break;

            case 4: printf("enter item=");

                    scanf("%d",&item);

                    push_stack2(item);

                    break;

            case 5: pop_stack2();

                    break;

            case 6: display_stack2();

                    break;

            case 7: printf("enter item=");

                    scanf("%d",&item);

                    push_stack3(item);

                    break;

            case 8: pop_stack3();

                    break;

            case 9: display_stack3();

                    break;

        }

        printf("enter choice=");

        scanf("%d",&choice);

    }while(choice!=10);

    return 0;

}

if you fing any bug related to code plzz post in comment thanks!!

MERGE TWO SORTED ARRAY

Q.) GIVEN TWO SORTED ARRAY MERGE THEM IN A SHORTED ARRAY .

TEST CASES

ARRAY 1 -> -10 12 100 141 240 

ARRAY 2-> -20 10 12 150 300 500 1932 

OUTPUT ARRAY -> -20 -10 10 12 12 100 141 150 240 300 500 1932

(ASKED IN AMAZON INTERVIEW)

#include
int main()
{
    int size_1,size_2,i;

    //enter the size of two ordered array//
    scanf("%d %d",&size_1,&size_2);
    int arr1[size_1],arr2[size_2],arr[size_1+size_2];

    //enter values in arr1//
    for(i=0;i<size_1;i++)
        scanf("%d",&arr1[i]);

    //enter values in arr2//
    for(i=0;i<size_2;i++)
        scanf("%d",&arr2[i]);
    int num_1=0,num_2=0;
    for(i=0;i<size_1+size_2;i++)
    {
        if(arr1[num_1]>arr2[num_2]&&num_2<size_2)
        {
            arr[i]=arr2[num_2];
            num_2=num_2+1;
 
        }
        else
        {
            arr[i]=arr1[num_1];
            num_1=num_1+1;
        }
    }

    // merged shorted array //
    for(i=0;i<size_1+size_2;i++)
        printf("%d ",arr[i]);
    return 0;
}

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