void permute(char *a, int i, int n) // i = starting index and n = number of
characters
{
if (i == n)
printf("%s\n", a);
else
{
for (int j = i; j <= n; j++)
{
swap(a[i], a[j]);
permute(a, i+1, n);
swap(a[i], a[j]); //backtrack
}
}
}
You can win three kinds of basketball points, 1 point, 2 points, and 3 points. Given a total score n, print out all the combination to compose n
At first position we can have three numbers 1 or 2 or 3. First put 1 at first position and recursively call for n-1. Then put 2 at first position and recursively call for n-2. Then put 3 at first position and recursively call for n-3.#define MAX_POINT 3voidprintArray(intarr[],intarr_size);void printCompositions(int n, int i) { static int arr[ARR_SIZE]; if (n == 0) { printArray(arr, i); } else if(n > 0) { int k; for (k = 1; k <= MAX_POINT; k++) { arr[i]= k; printCompositions(n-k, i+1); } } }
Take the set of integers
1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,……
First, delete every second number, we get following reduced set.
1,3,5,7,9,11,13,15,17,19,…………
Now, delete every third number, we get
1, 3, 7, 9, 13, 15, 19,….….
Continue this process indefinitely……
Any number that does NOT get deleted due to above process is called “lucky”.
Therefore, set of lucky numbers is 1, 3, 7, 13,………
CODE
bool isLucky(int n)
{
int next_pos = n, counter;
for(counter=2; counter <= next_pos; ++counter)
{
if(next_pos%counter == 0)
return 0;
next_pos -= next_pos/counter;
}
return 1;
}
int pow(int a, int b)
{
if(b)
return multiply(a, pow(a, b-1));
else
return 1;
}
int multiply(int x, int y)
{
if(y)
return (x + multiply(x, y-1));
else
return 0;
}
N<<3 gives 8n and subtract by n to get 7n
Each n bit shift will multibly by (2 ^ n)
((n<<3) - n) // works for positive number only
QUESTION
You have a rectangular chocolate bar that consists of width x height square tiles. You can split it into two rectangular pieces by creating a single vertical or horizontal break along tile edges. For example, a 2 x 2 chocolate bar can be divided into two 2 x 1 pieces, but it cannot be divided into two pieces, where one of them is 1 x 1. You can repeat the split operation as many times as you want, each time splitting a single rectangular piece into two rectangular pieces. Your goal is to create a piece consisting of exactly nTiles tiles. Return the minimal number of split operations necessary to reach this goal. If it is impossible, return -1.
ANSWER
We first note that if we have a possible final rectangle we can easily determine the number of splits necessary to create the rectangle. If it is the same rectangle as the original one it requires zero splits; if only one of the lengths of the final rectangle is equal to one of the lengths of the original rectangle it requires one split; and otherwise, it requires two splits. We can iterate over the side of the smallest side of the final rectangle and we will call its length a. The length of the other side of the final rectangle must be of size b=nTiles/a, and it must be an integer. Since a<=b, we get at most sqrt(nTiles) possible final rectangles. For each possible final rectangle we have to check if it fits in the original rectangle — if it does, we have to calculate the number of split operations necessary and update our best result so far. In the end, we return the best result found, or -1 if we have found no valid rectangle.
CODE
int minSplitNumber(int width, int height, int nTiles) {
if((long long)width*height<nTiles) return -1;
if((long long)width*height==nTiles) return 0;
if(nTiles%width==0||nTiles%height==0) return 1;
for(int a=1;a*a<=nTiles;++a) if(nTiles%a==0) {
int b=nTiles/a;
if(a<=width&&b<=height||a<=height&&b<=width)
return 2;
}
return -1;
}
A k-double string is a non-empty string consisting of two equal length halves, where the first half differs from the second half at no more than k positions. For example, “contestcontest”, “oopoop” and “aa” are 0-double strings. “contestkontest” is a 1-double string, and “poorpork”, “artbat”, and “yesyep” are 2-double strings. Obviously, all 0-double strings are also 1-double strings, all 1-double strings are also 2-double strings, etc.
You will be given a String[] str and an int k. Concatenate the elements of str to form one long string, and return the number of k-double substrings contained in that string.
Example:-
{“contest”, “kontest”}
1
Returns: 14
Each pair of consecutive letters form a 1-double substring and the whole string form one more 1-double substring.
CODE
int howMuch(vector <string> str, int k) {
string s;
for(int i=0;i<str.size();++i)
s+=str[i];
int n=s.size();
int ret=0;
for(int a=0;a<n;++a)
for(int b=a;b<n;++b) {
int len=b-a+1;
if(len%2!=0)
continue;
int half=len/2;
int cnt=0;
for(int i=0;i<half;++i)
if(s[a+i]!=s[a+half+i])
++cnt;
if(cnt<=k)
++ret;
}
return ret;
}
int lis( int arr[], int n )
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );
for ( i = 0; i < n; i++ )
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
// To get Max element in lis[]
for ( i = 0; i < n; i++ )
if ( max < lis[i] )
max = lis[i];
free( lis );
return max;
}
Test case
{ 10, 22, 9, 33}
i=1 j=0
lis[1] = 2
i=2 j=0 i=2 j=1
no change
i=3 j=0 i=3 j=1 i=3 j=2
lis[3] =2 lis[3] =3
max = 3
String s = "Hello World!";
for(int i = 0; i < s.length(); i++)
{
s = s.substring(1, s.length() - i) + s.charAt(0) + s.substring(s.length() - i);
}
System.out.println(s);
OR
String str = "Hello World!"; int len = str.length(); for (int i = (len-1); i >= 0; --i) str += str.charAt(i); str = str.substring(len); System.out.println(str);
int dayofweek(int d, int m, int y)
{
static int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
y -= m < 3; // m < 3 is either 1 or 0
// So y=y-1 when m<3 or y=y-0 when m>=3
return ( y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}
Explanation
Assume now that leap years did not exist and every year had 365 days.
Knowing what day January 1 falls on a certain year, it is easy to find which day any other date falls. January has 31 = 7 × 4 + 3 days, so February 1 will fall on the day which follows three days after January 1. Similarly, March 1 will fall on the day three days after the day corresponding to January 1, April 1 will fall 6 days after, and so on. Thus, the first days of each month are offset with respect to January 1 by the array t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}.. Different from the original t[] given in the question is due to leap years which will be explained later.
Since 365 = 7 × 52 + 1, the day corresponding to a given date will become incremented by 1 every year. For example, July 14, 2014 is a Monday and July 14, 2015 will be a Tuesday. Hence adding the difference between year numbers allows us to switch from the day of a reference year to any other year.
At this stage, the leap-year free dow function can be written as such:
int dow(int y, int m, int d){
static int t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};
return (y + t[m-1] + d) % 7;
}
Considering leap years
Every 4 years, our calculation will gain one extra day. Except every 100 years when it doesn’t. Except every 400 years when it does . Just adding y/4 – y/100 + y/400 works gives exactly the required number of leap days.
Except one problem. The leap day is not January 0, it is February 29. This means that the current year should not be counted for the leap day calculation for the first two months.
Suppose that if the month were January or February, we subtracted 1 from the year. This means that during these months, the y/4 value would be that of the previous year and would not be counted.
Except for a tiny problem. We are subtracting 1 from the year for January and February for non-leap years too. This means that there would be a “blank” day between February 28 and March 1, that is, we have made every non-leap year a leap year, and leap years double-leap years. So we subtracted 1 from the t[] values of every month after February? That would fill the gap, and the leap year problem is solved. That is, we need to make the following changes:
• t[] now becomes {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}
• if m corresponds to Jan/Feb (that is, m<3) we decrement y by 1
• the annual increment inside the modulus is now y + y/4 – y/100 + y/400 in place of y
Learn By Coding 