Euler Totient Function

SPOJ Problem Set (classical)

4141. Euler Totient Function

Problem code: ETF

English Vietnamese
In number theory, the totient  of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Given an integer n (1 <= n <= 10^6). Compute the value of the totient .

Input

First line contains an integer T, the number of test cases. (T <= 20000)

T following lines, each contains an integer n.

Output

T lines, one for the result of each test case.

Example

Input:
5
1
2
3
4
5

Output:
1
1
2
2
4



EXPLAINATION--
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers

(TOPCODER FORUM)

SOLUTION--

#include
int phi(int n)
{
     int result = n;
     int i;
       for(i=2;i*i <= n;i++) 
       { 
         if (n % i == 0) 
         result -= result / i; 
         while (n % i == 0) 
         n /= i; 
       } 
       if (n > 1)
       result -= result / n; 
       return result; 
}
int main()
{
    int t,num;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&num);
        printf("%d\n",phi(num));
    }
    return 0;
}

GCD

SPOJ Problem Set (classical)

2906. GCD2

Problem code: GCD2

Frank explained its friend Felman the algorithm of Euclides to calculate the GCD of two numbers. Then Felman implements it algorithm

int gcd(int a, int b)
{
if (b==0)
return a;
else
return gcd(b,a%b);
}
and it proposes to Frank that makes it but with a little integer and another integer that has up to 250 digits.
Your task is to help Frank programming an efficient code for the challenge of Felman.

Input

The first line of the input file contains a number representing the number of lines to follow. Each line consists of two number A and B (0 <= A <= 40000 and A <= B < 10^250).

Output

Print for each pair (A,B) in the input one integer representing the GCD of A and B.

Example

Input:
2
2 6
10 11


Output:
2
1

EXPLAINATION--
In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.


SOLUTION---

#include
#include
int mod(char str[],int d)
{
    int r=0,i;
    for(i=0;str[i];i++)
    {
        r=10*r+(str[i]-'0');
        r=r%d;
    }
    return r;
}
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        gcd(b,a%b);
}
int main()
{
    int t,a;
    char str[255];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&a);
        scanf("%s",str);
        if(a==0)
            printf("%s\n",str);
        else if(str[0]=='0')
            printf("%d\n",a);
        else
        {
            printf("%d\n",gcd(a,mod(str,a)));   
        }
    }
    return 0;
}
 
 

CREATION OF BST

CREATION OF BINARY SEARCH TREE.

BINARY SEARCH HAS PROPERTIES-

1.)The left subtree of a node contains only nodes with keys less than the node's key.
2.)The right subtree of a node contains only nodes with keys greater than the node's key.
3.)Both the left and right subtrees must also be binary search trees.
4.) There must be no duplicate nodes.

#include 
typedef struct tnode
{
    int data;
    struct tnode *right,*left;
}TNODE;
 
TNODE *CreateBST(TNODE *, int);
void Inorder(TNODE *);
void Preorder(TNODE *);
void Postorder(TNODE *);
main()
{
    TNODE *root=NULL;   /* Main Program */
    int opn,elem,n,i;
    do
    {
        printf("\n ### Binary Search Tree Operations ### \n\n");
        printf("\n Press 1-Creation of BST");
        printf("\n       2-Traverse in Inorder");
        printf("\n       3-Traverse in Preorder");
        printf("\n       4-Traverse in Postorder");
        printf("\n       5-Exit\n");
        printf("\n       Your option ? ");
        scanf("%d",&opn);
        switch(opn)
        {
        case 1: root=NULL;
            printf("\n\nBST for How Many Nodes ?");
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                printf("\nRead the Data for Node %d ?",i);
                scanf("%d",&elem);
                root=CreateBST(root,elem);
            }
            printf("\nBST with %d nodes is ready to Use!!\n",n);
            break;
        case 2: printf("\n BST Traversal in INORDER \n");
            Inorder(root); break;
        case 3: printf("\n BST Traversal in PREORDER \n");
            Preorder(root); break;
        case 4: printf("\n BST Traversal in POSTORDER \n");
            Postorder(root); break;
        case 5: printf("\n\n Terminating \n\n"); break;
        default: printf("\n\nInvalid Option !!! Try Again !! \n\n");
            break;
        }
        
        }while(opn != 5);
}
TNODE *CreateBST(TNODE *root, int elem)
{
    if(root == NULL)
    {
        root=(TNODE *)malloc(sizeof(TNODE));
        root->left= root->right = NULL;
        root->data=elem;
        return root;
    }
    else
    {
        if( elem < root->data )
            root->left=CreateBST(root->left,elem);
        else
            if( elem > root->data )
                root->right=CreateBST(root->right,elem);
            else
                printf(" Duplicate Element !! Not Allowed !!!");
 
        return(root);
    }
}
void Inorder(TNODE *root)
{
    if( root != NULL)
    {
        Inorder(root->left);
        printf(" %d ",root->data);
        Inorder(root->right);
    }
}
 
void Preorder(TNODE *root)
{
    if( root != NULL)
    {
        printf(" %d ",root->data);
        Preorder(root->left);
        Preorder(root->right);
    }
}
 
void Postorder(TNODE *root)
{
    if( root != NULL)
    {
        Postorder(root->left);
        Postorder(root->right);
        printf(" %d ",root->data);
    }
}

if you find any bugs related to above program the plzz cmnt :)

thnxx!!

EDIT DISTANCE AGAIN

SPOJ Problem Set (classical)

10537. Edit Distance Again

Problem code: EDIT



As any experienced programmer must know the famous problem of "Edit Distance", however thisproblem is considered an “alternating chain” if you have alternately made case sensitive.Example:"AaAaAbB" "B" "a" "aBaCdEf"Alternating chains are considered in our problem.We only have one operation that is permitted in exchange for a lower or upper case Latin letter.Given a string giving the minimum number of changes to be considered an alternating chain.


As any experienced programmer must know the famous problem of "Edit Distance", however this

problem is considered an “alternating chain” if you have alternately made case sensitive.

Example:

"AaAaAbB" "B" "a" "aBaCdEf"

Alternating chains are considered in our problem.

We only have one operation that is permitted in exchange for a lower or upper case Latin letter.

Given a string giving the minimum number of changes to be considered an alternating chain.





Input



A string with no spaces line containing only uppercase and lowercase letters, one for each line of

maximum length 10 ^ 3 until end of file



Output



For each line print the minimum number of changes to the chain is a "chain alternately"



Example

Input:
AaAaB
ABaa
a

Output:
0
2
0

-----------------------------------------------------------------
treat capital letter as '1' and small letters as'0' and create a binary representation of input string .
for e.g
given string is "AaaaBbB"
then binary representation is -- 1000101(arr1)
now there is two way to generate alternating chain 
1st one is 0101010(arr2)
2nd one is 1010101(arr3)
now compare this two alternating chains with the arr1(generated acc, to input string )
now find the bit difference of arr1 with arr2 and arr3.
let say the bit diff. of arr1 and arr2 is count1 and the bit differnce of arr1 and arr3 is count3
now find minimum of count1 and count2 
print that value .
Question solved :)



SOURCE CODE--

#include
#include
int main()
{
    char str[1005];
    int len,i,count1,a,count2;
    while(scanf("%s",str)!=EOF)
    {
        len=strlen(str);
        int arr1[len];
        int arr2[len];
        int arr3[len];
        count1=0,count2=0;
        if(len==1)
            printf("0\n");
        else
        {
            for(i=0;i<len;i++)
            {
                a=str[i];
               // printf("%d ",a);
                if(a>=65&&a<=90)
                    arr1[i]=1;
                else
                    arr1[i]=0;
            }
 
            a=str[0];
            if(a>=65&&a<=90){
                arr2[0]=1;
                arr3[0]=0;
            }
            else{
                arr2[0]=0;
                arr3[0]=1;
            }
            for(i=1;i<len;i++)
            {
                if(arr2[i-1]==0)
                {
                    arr2[i]=1;
                    arr3[i]=0;
                }
                else{
                    arr2[i]=0;
                    arr3[i]=1;
                }
            }
            /*for(i=0;i
                printf("%d ",arr1[i]);
            printf("\n");
            for(i=0;i
                printf("%d ",arr2[i]);*/
            for(i=0;i<len;i++)
            {
                if(arr1[i]!=arr2[i])
                    count1+=1;
                if(arr1[i]!=arr3[i])
                    count2+=1;
            }
            printf("%d\n",(count1<count2)?count1:count2);
        }
    }
    return 0;
}
 

AMUSING NUMBER (TSHOW1)

SPOJ Problem Set (classical)

11354. Amusing numbers

Problem code: TSHOW1

Amusing numbers are numbers consisting only of digits 5 and 6.Given an integer k , display the kth amusing number.

Input

FIrst line consists of integer N representing number of test cases

Next N lines consist of N integers (1<=k<=10^15)

Output

N lines each displaying corresponding kth amusing number

Example

Input:
2
1
5
Output:
5
65 



EXPLAINATION--

the sequence is : 5 , 6, 55, 56, 65, 66, 555, 565…

if we break the sequence by the length of each number i.e 5 and 6 are of length 1  whereas 55, 56 are of

length 2 and so on, it would make the problem easier to tackle. Suppose for time being we know that the

Kth  amusing number is of length x digits. We also magically know that its the Nth  number of length x.

(5 is the first number of length 1, 56 is second number of length 2 and so on…)

Then we can easily find the kth number by representing  the number (N-1) in its binary equivalent where

0 of binary stands for 5 and 1 of binary represents 6.

For instance : We need to find 5th amusing number and some how we  know it would be of length 2(x=2)

and 3rd(N=3) number of length  2.

Binary representation of N-1 =2 is : 10 , Replacing 0 by 5 and 1 by 6 we get : 65 which is the answer!

Now to find of what length the kth amusing number would be we  need to solve a GP.

There are 2 numbers of length 1,  4 numbers of length 2 , 8 numbers of length 3 and so on…

This is a GP  from which  we can easily find what length would be the kth amusing number and corresponding

value of N .

SERIES HINT--

KTH NUMBER  BINARY REPRESENTAION    AMUSING NUMBER

1                0                         5

2                1                         6

3               00                        55

4               01                        56

5               10                        65

6               11                        66

7              000                       555

8              001                       556

9              010                       565

10             011                       566

11             100                       655

12             101                       656

13             110                       665

14             111                       666

15            0000                      5555

16            0001                      5556

17            0010                      5565

18            0011                      5566

19            0100                      5655

20            0101                      5656

21            0110                      5665

22            0111                      5666

23            1000                      6555

24            1001                      6556

25            1010                      6565

26            1011                      6566

27            1100                      6655

28            1101                      6656

29            1110                      6665

30            1111                      6666

SOURCE CODE--

#include
#include
int main()
{
    int t;
    long long int num,temp,n,i,j,ans,k,rem;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&num);
        temp=0,n=0;

        //calculating the value of n(length)
        while(temp<num)
        {
            n=n+1;
            temp=pow(2,n+1)-2;
            //printf("%lld ",temp);
        }
        temp=pow(2,n)-2;
        //printf("%lld %lld\n",n,temp);
        ans=num-temp-1;
        char str[100000];
        int k=-1;

        //converting the number in binary representation
        while(ans>0)
        {
            rem=ans%2;
            k=k+1;
            str[k]=rem+'0';
            ans=ans/2;
        }
        j=n-k-1;
        for(i=1;i<=j;i++)
            printf("5");

        //print 5 inplace of '0' and print 6 in place of '1'
        for(i=k;i>=0;i--){
            if(str[i]=='0')
                printf("5");
            else
                printf("6");
        }
        printf("\n");
    }
    return 0;
}