Program to generate Permutations

  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<string.h>
  5. using namespace std;
  6. void permute(char *a, int i, int n)
  7. {
  8. int j;
  9. if (i == n)
  10. cout<<a<<endl;
  11. else
  12. {
  13. for (j = i; j <= n; j++)
  14. {
  15. swap(a[i],a[j]);
  16. permute(a, i+1, n);
  17. swap(a[i],a[j]); //backtrack
  18. }
  19. }
  20. }
  21. int main()
  22. {
  23. char a[100];
  24. int len;
  25. cin>>a;
  26. len=strlen(a);
  27. permute(a, 0, len-1);
  28. return 0;
  29. }
Advertisements

Vampire Number Problem

Question: A vampire number has an even number of digits and is formed by multiplying a pair of numbers containing half the number of digits of the result. The digits are taken from the original number in any order. Pairs of trailing zeroes are not allowed.

Example include:
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81

  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<math.h>
  4. using namespace std;
  5. bool check(int a,int b);
  6. int t;
  7. int ct=0;
  8. int num[10]={0};
  9. bool check(int a,int b);
  10. int main()
  11. {
  12. int i,flag=0,a,x,n;
  13. cin>>t;
  14. x=t;
  15. while(x!=0)
  16. {
  17. a=x%10;
  18. ct++;
  19. num[a]++;
  20. x/=10;
  21. }
  22. n=sqrt(t);
  23. for(i=1;i<=n;i++)
  24. {
  25. if(t%i==0)
  26. {
  27. if(check(i,t/i)){cout<<i<<” “<<t/i<<endl;flag=1;}
  28. }
  29. }
  30. if(flag)cout<<“yes\n”;
  31. else cout<<“no\n”;
  32. return 0;
  33. }
  34. bool check(int a,int b)
  35. {
  36. int x,y,i,ct1=0,ct2=0;
  37. int num1[10]={0};
  38. while(a!=0)
  39. {
  40. x=a%10;
  41. ct1++;
  42. num1[x]++;
  43. a/=10;
  44. }
  45. if(ct1!=ct/2)return 0;
  46. while(b!=0)
  47. {
  48. y=b%10;
  49. ct2++;
  50. num1[y]++;
  51. b/=10;
  52. }
  53. if(ct2!=ct/2)return 0;
  54. for(i=0;i<10;i++)
  55. {
  56. if(num[i]!=num1[i])return 0;
  57. }
  58. return 1;
  59. }

String Problem

Question:A string  is entered through the keyboard,.

Write a program  to get its reverse (word by word) in a column as output .

Example:

Input: I am writing an email

Ouput:
email
an
writing
am
I

  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. using namespace std;
  5. struct ex
  6. {
  7. char b[1000];
  8. }t[1000];
  9. int main()
  10. {
  11. int i=0,j;
  12. char s[1000],a[1000];
  13. gets(s);
  14. int z=0;
  15. while(i<strlen(s))
  16. {
  17. memset(a,0,1000);
  18. j=0;
  19. while(s[i]!=’ ‘)
  20. {
  21. a[j]=s[i];
  22. j++;
  23. i++;
  24. }
  25. i++;
  26. a[j]=”;
  27. strcpy(t[z].b,a);
  28. z++;
  29. }
  30. for(i=z-1;i>=0;i–)
  31. cout<<t[i].b<<endl;
  32. return 0;
  33. }

C++ Program to Check If Given String Is Of Form a^n b^n c^n Where n>=1

  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. using namespace std;
  5. int main()
  6. {
  7.    char a[50];
  8.    int i,j,k,len;
  9.    cout<<“Enter the string to check\n”; //input the string
  10.    cin>>a;
  11.    if(strlen(a)%3!=0)  //if string length is not multiple of 3 , reject it
  12.    {
  13.        cout<<“Not accepted\n”;
  14.        exit(0);
  15.    }
  16.    len=strlen(a)/3;  //len= length of the input string
  17.    for(i=0;i
  18.    {
  19.        if(a[i]!=’a’)
  20.        {
  21.            cout<<“Not accepted\n”;
  22.            exit(0);
  23.        }
  24.    }
  25.    for(j=i;j<i+len;j++)  //checks if next len/3 characters are ‘b’
  26.    {
  27.        if(a[j]!=’b’)
  28.        {
  29.            cout<<“Not accepted\n”;
  30.            exit(0);
  31.        }
  32.    }
  33.    for(k=j;k<j+len;k++)  //checks if next len/3 characters are ‘c’
  34.    {
  35.        if(a[k]!=’c’)
  36.        {
  37.            cout<<“Not accepted”;
  38.            exit(0);
  39.        }
  40.    }
  41. /*if all conditions are satisfied, it shows that input is accepted*/
  42.    cout<<“Accepted\n”;
  43.    return 0;
  44. }

Output:

Enter the string to check

aabbcc

Accepted

Codechef Odd( DCE05 ) Problem

Problem Statement:

The captain of the ship TITANIC is a little …. off the track. He needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game.

The contestants have to stand in a line. They are given the numbers in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position.

Initially, standing people have numbers – 1,2,3,4,5…
After first pass, people left are – 2,4,…
After second pass – 4,….
And so on.

You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in the line so that you are selected.

Input

First line contains the number of test cases t (t<=10^5). The next t lines contain integer n, the number of applicants for that case. (n<=10^9)

Output

Display t lines, each containing a single integer, the place where you would stand to win a place at TITANIC.

Here is the link to the problem:

http://www.codechef.com/problems/DCE05

Solution:

  1. #include<iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4. int main()
  5. {
  6.  int t,n,z=1;
  7.  scanf(“%d”,&t);
  8.   while(t–)
  9.   {
  10.   z=1;
  11.     scanf(“%d”,&n);
  12.    while(z<=n)
  13.       z*=2;
  14.      printf(“%d\n”,z/2);
  15.   }
  16.   return 0;
  17. }

Project Euler Problem 17

Here is the problem statement:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

Here is the link to the question:

Solution:

What i did is , i converted each number to its word form and added its value.

Here is the code:

  1. #include<iostream>
  2. #include<string.h>
  3. using namespace std;
  4. void pw(long n,int x);
  5. /*Integer array one stores number of letters in each word starting from 1 to 19*/
  6. int one[]={0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,7,9,8,8};
  7. /*Integer array ten number of letters for each word starting from twenty till ninety*/
  8. int ten[]={0,0,6,6,5,5,5,7,6,6};
  9. int sum=0;
  10. int main()
  11. {
  12.     int i;
  13.     for(i=1;i<=1000;i++)
  14.        {
  15.             pw(((i/1000)%100),8);
  16.             pw(((i/100)%10),7);
  17.             pw((i%100),0);
  18.         }
  19.  /* adding 2673 for taking into account “and” which appear 99*9 times , so total length wud be 99*9*3*/
  20.     cout<<sum+2673<
  21.     return 0;
  22. }
  23.  
  24. void pw(long n,int x)
  25. {
  26. if(n>19){sum+=ten[n/10]+one[n%10];}//basically to get digit/digits at a time
  27. else
  28. {
  29.     sum+=one[n];
  30. }
  31. if(n)sum+=x;
  32. }


Output:

21124

C++ Program to implement N-Queens Problem

In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen’s problem asks how to place 8 queens on an ordinary chess board so that none of them can hit any other in one move. Consider an N by N “chess board” and ask if one can place N queens on such a board

Here is the code for it:

  1. #include<iostream>
  2. #include<vector>
  3. #include<fstream>
  4. #include<string>
  5. #include<algorithm>
  6. using namespace std;
  7. int ct=0;
  8. class queen
  9. {
  10.     int n;
  11. public:
  12.     void read()
  13.     {
  14.         cout<<“Enter board size\n”;
  15.         cin>>n;
  16.     }
  17.     bool place(int x[10],int k)
  18.     {
  19.         for(int i=1;i<k;i++)
  20.         {
  21.             if(x[i]==x[k]||i+x[i]==k+x[k]||i-x[i]==k-x[k])
  22.                 return false;
  23.         }
  24.         return true;
  25.     }
  26.     void nqueen()
  27.     {
  28.         int x[10];
  29.         int k=1;
  30.         x[k]=0;
  31.         while(k!=0)
  32.         {
  33.             x[k]++;
  34.             while((!place(x,k))&&(x[k]<=n))x[k]++;
  35.         if(x[k]<=n)
  36.         {
  37.             if(k==n)
  38.             {
  39.                 ct++;
  40.                 cout<<“Solution “<<ct<<“:\n”;
  41.                 print(x);
  42.                 cout<<endl;
  43.             }
  44.             else
  45.             {
  46.                 k++;
  47.                 x[k]=0;
  48.             }
  49.         }
  50.         else
  51.             k–;
  52.         }
  53.     }
  54.     void print(int x[10])
  55.     {
  56.         char c[10][10];
  57.         for(int i=1;i<=n;i++)
  58.         {
  59.             for(int j=1;j<=n;j++)
  60.                 c[i][j]=’X’;
  61.         }
  62.         for(int i=1;i<=n;i++)
  63.         {
  64.             c[i][x[i]]=’Q’;
  65.         }
  66.         for(int i=1;i<=n;i++)
  67.         {
  68.             for(int j=1;j<=n;j++)
  69.                 cout<<c[i][j];
  70.                 cout<<endl;
  71.         }
  72.         cout<<endl;
  73.     }
  74. };
  75. int main()
  76. {
  77.     queen A;
  78.     A.read();
  79.     A.nqueen();
  80.     return 0;
  81. }

 

Output:

Enter board size

4

Solution 1:

XQXX

XXXQ

QXXX

XXQX

 

Solution 2:

XXQX

QXXX

XXXQ

XQXX