Hacker Rank Solution For Utopian-Tree

Utopian-Tree

The Utopian tree goes through 2 cycles of growth every year. The first growth cycle of the tree occurs during the monsoon, when it doubles in height. The second growth cycle of the tree occurs during the summer, when its height increases by 1 meter.
Now, a new Utopian tree sapling is planted at the onset of the monsoon. Its height is 1 meter. Can you find the height of the tree after N growth cycles?

Input Format
The first line contains an integer, T, the number of test cases.
T lines follow. Each line contains an integer, N, that denotes the number of cycles for that test case.

Constraints 
1 <= T <= 10
0 <= N <= 60

 Output Format 
For each test case, print the height of the Utopian tree after N cycles.

Sample Input #00:
2
0
1

Sample Output #00:

1
2
Explanation #00:
There are 2 test cases. When N = 0, the height of the tree remains unchanged. When N = 1, the tree doubles its height as it's planted just before the onset of monsoon.


Sample Input: #01:

2
3
4

 Sample Output: #01:

6
7

 Explanation: #01: 

There are 2 testcases.
N = 3:
the height of the tree at the end of the 1st cycle = 2
the height of the tree at the end of the 2nd cycle = 3
the height of the tree at the end of the 3rd cycle = 6

N = 4:
the height of the tree at the end of the 4th cycle = 7


SOLUTION 


#include<stdio.h>
int main()
    {
    int T, N[10],m,i,j;
    scanf("%d",&T);
    for(i=0;i<T;i++){
        scanf("%d",&N[i]);
        m=1;
        if(N[i]!=0){
        for(j=1;j<=N[i];j++) {
            if(j%2!=0)
                m=2*m;
            else
                m=m+1;
        }}
        printf("%d \n",m);
    }
    return 0;
}



Posted by 10 comments:

Hacker Rank Solution For Utopian-Tree

Hacker Rank Solution For Utopian-Tree

The Utopian tree goes through 2 cycles of growth every year. The first growth cycle of the tree occurs during the monsoon, when it doubles in height. The second growth cycle of the tree occurs during the summer, when its height increases by 1 meter.
Now, a new Utopian tree sapling is planted at the onset of the monsoon. Its height is 1 meter. Can you find the height of the tree after N growth cycles?

Input Format
The first line contains an integer, T, the number of test cases.
T lines follow. Each line contains an integer, N, that denotes the number of cycles for that test case.

Constraints 
1 <= T <= 10
0 <= N <= 60

 Output Format 
For each test case, print the height of the Utopian tree after N cycles.

Sample Input #00:
2
0
1

Sample Output #00:

1
2
Explanation #00:
There are 2 test cases. When N = 0, the height of the tree remains unchanged. When N = 1, the tree doubles its height as it's planted just before the onset of monsoon.


Sample Input: #01:

2
3
4

 Sample Output: #01:

6
7

 Explanation: #01: 

There are 2 testcases.
N = 3:
the height of the tree at the end of the 1st cycle = 2
the height of the tree at the end of the 2nd cycle = 3
the height of the tree at the end of the 3rd cycle = 6

N = 4:
the height of the tree at the end of the 4th cycle = 7


SOLUTION 


#include<stdio.h>
int main()
    {
    int T, N[10],m,i,j;
    scanf("%d",&T);
    for(i=0;i<T;i++){
        scanf("%d",&N[i]);
        m=1;
        if(N[i]!=0){
        for(j=1;j<=N[i];j++) {
            if(j%2!=0)
                m=2*m;
            else
                m=m+1;
        }}
        printf("%d \n",m);
    }
    return 0;
}




Posted by 1 comment:

DAA LAB PROGRAMS

Posted by 9 comments:

SUM OF SUBSET PROBLEM

         ||DAA Lab program for  subset sum problem||

 // A recursive solution for subset sum problem
#include <stdio.h>

// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
   // Base Cases
   if (sum == 0)
     return true;
   if (n == 0 && sum != 0)
     return false;

   // If last element is greater than sum, then ignore it
   if (set[n-1] > sum)
     return isSubsetSum(set, n-1, sum);

   /* else, check if sum can be obtained by any of the following
      (a) including the last element
      (b) excluding the last element   */
   return isSubsetSum(set, n-1, sum) ||
                        isSubsetSum(set, n-1, sum-set[n-1]);
}

// Driver program to test above function
int main()
{
  int set[] = {3, 34, 4, 12, 5, 2};
  int sum = 9;
  int n = sizeof(set)/sizeof(set[0]);
  if (isSubsetSum(set, n, sum) == true)
     printf("Found a subset with given sum");
  else
     printf("No subset with given sum");
  return 0;
}

 OUTPUT

  Found a subset with given sum 
Posted by 1 comment:

Design and Analysis of Algorithms Lab Programs for Engineering

Posted by 2 comments:

DAA Lab program to implement N Queen Problem using Backtracking

DAA LAB Program 11

Write a program to implement N Queen Problem using Backtracking

#include<stdio.h>
#include<conio.h>
#include<math.h>
char a[10][10];
int n;
void printmatrix()
{
int i, j;
printf("\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
printf("%c\t", a[i][j]);
printf("\n\n");
}
}
int getmarkedcol(int row)
{
int i;
for (i = 0; i < n; i++)
if (a[row][i] == 'Q')
{
return (i);
break;
}
}
int feasible(int row, int col)
{
int i, tcol;
for (i = 0; i < n; i++)
{
tcol = getmarkedcol(i);
if (col == tcol || abs(row - i) == abs(col - tcol))
return 0;
}
return 1;
}
void nqueen(int row)
{
int i, j;
if (row < n)
{
for (i = 0; i < n; i++)
{
if (feasible(row, i))
{
a[row][i] = 'Q';
nqueen(row + 1);
a[row][i] = '.';
}
}
}
else
{
printf("\nThe solution is:- ");
printmatrix();
}
}
void main()
{
clrscr();
int i, j;
printf("\nEnter the no. of queens:- ");
scanf("%d", &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] = '.';
nqueen(0);
getch();
}


OUTPUT
Posted by No comments:

DAA Lab program to find Minimum Spanning Tree using Kruskal’s Algorithm

DAA LAB Program 10

Write a program to find Minimum Spanning Tree using Kruskal’s Algorithm

#include<stdio.h>
#include<conio.h>
#define INF 0
char vertex[10];  
int wght[10][10];
int span_wght[10][10];
int source;
struct Sort
{
int v1,v2;
int weight;
}que[20];
int n,ed,f,r;
int cycle(int s,int d)
{
int j,k;
if(source==d)
return 1;
for(j=0;j<n;j++)
if(span_wght[d][j]!=INF && s!=j) 
{
if(cycle(d,j))
return 1;
}
return 0;
}
void build_tree()
{
int i,j,w,k,count=0;
for(count=0;count<n;f++)
{
i=que[f].v1;
j=que[f].v2;
w=que[f].weight;
span_wght[i][j]=span_wght[j][i]=w;
source=i;
k=cycle(i,j);
if(k)
span_wght[i][j]=span_wght[j][i]=INF;
else
count++;
}
}
void swap(int *i,int *j)
{
int t;
t=*i;
*i=*j;
*j=t;
}
void main()
{
int i,j,k=0,temp;
int sum=0;
clrscr();
printf("\n\tEnter the No. of Nodes : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n\tEnter %d value : ",i+1);
fflush(stdin);
scanf("%c",&vertex[i]);
for(j=0;j<n;j++)
{
wght[i][j]=INF;
span_wght[i][j]=INF;
}
}
printf("\n\nGetting Weight\n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
printf("\nEnter 0 if path Doesn't exist between %c to %c : ",vertex[i],vertex[j]);
scanf("%d",&ed);
if(ed>=1)
{
wght[i][j]=wght[j][i]=ed;
que[r].v1=i;
que[r].v2=j;
que[r].weight=wght[i][j];
if(r)
{
for(k=0;k<r;k++)
if(que[k].weight>que[r].weight)
{
swap(&que[k].weight,&que[r].weight);
swap(&que[k].v1,&que[r].v1);
swap(&que[k].v2,&que[r].v2);
}
}
r++;
}
}
clrscr();
printf("\n\tORIGINAL GRAPH WEIGHT MATRIX\n\n");
printf("\n\tweight matrix\n\n\t");
for(i=0;i<n;i++,printf("\n\t"))
for(j=0;j<n;j++,printf("\t"))
printf("%d",wght[i][j]);
build_tree();
printf("\n\n\t\tMINIMUM SPANNING TREE\n\n");
printf("\n\t\tLIST OF EDGES\n\n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(span_wght[i][j]!=INF)
{
printf("\n\t\t%c ------ %c = %d ",vertex[i],vertex[j],span_wght[i][j]);
sum+=span_wght[i][j];
}
printf("\n\n\t\tTotal Weight : %d ",sum);
getch();
}


 OUTPUT




Posted by No comments:

DAA Lab program to perform Travelling Salesman Problem

DAA LAB Program 9

Write a program to perform Travelling Salesman Problem

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int a[10][10],visited[10],n,cost=0;
void get()
{
int i,j;
printf("\n\nEnter Number of Cities: ");
scanf("%d",&n);
printf("\nEnter Cost Matrix: \n");
for( i=0;i<n;i++)
{
printf("\n Enter Elements of Row # : %d\n",i+1);
for( j=0;j<n;j++)
scanf("%d",&a[i][j]);
visited[i]=0;
}
printf("\n\nThe Cost Matrix is:\n");
for( i=0;i<n;i++)
{
printf("\n\n");
for(j=0;j<n;j++)
printf("\t%d",a[i][j]);
}
}
void mincost(int city)
{
int i,ncity,least(int city);
visited[city]=1;
printf("%d ===> ",city+1);
ncity=least(city);
if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=a[city][ncity];
return;
}
mincost(ncity);
}
int least(int c)
{
int i,nc=999;
int min=999,kmin;
for(i=0;i<n;i++)
{
if((a[c][i]!=0)&&(visited[i]==0))
if(a[c][i]<min)
{
min=a[i][0]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost+=kmin;
return nc;
}
void put()
{
printf("\n\nMinimum cost:");
printf("%d",cost);
}
void main()
{
clrscr();
get();
printf("\n\nThe Path is:\n\n");
mincost(0);
put();
getch();

}

OUTPUT

Posted by 1 comment:

DAA Lab program to perform Knapsack Problem using Greedy Solution

DAA LAB  Program 8

Write a program to perform Knapsack Problem using Greedy Solution

#include<stdio.h>
#include<conio.h>
void knapsack(int n, float weight[], float profit[], float capacity)
{
float x[20], tp = 0;
int i, j, u;
u = capacity;
for (i = 0; i < n; i++)
x[i] = 0.0;
for (i = 0; i < n; i++)
{
if (weight[i] > u)
break;
else
{
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}
if (i < n)
x[i] = u / weight[i];
tp = tp + (x[i] * profit[i]);
printf("\nThe result vector is:- ");
for (i = 0; i < n; i++)
printf("%f\t", x[i]);
printf("\nMaximum profit is:- %f", tp);
}
void main()
{
clrscr();
float weight[20], profit[20], capacity;
int num, i, j;
float ratio[20], temp;
printf("\nEnter the no. of objects:- ");
scanf("%d", &num);
printf("\nEnter the weights and profits of each object:- ");
for (i = 0; i < num; i++)
{
scanf("%f %f", &weight[i], &profit[i]);
}
printf("\nEnter the capacity of knapsack:- ");
scanf("%f", &capacity);
for (i = 0; i < num; i++)
{
ratio[i] = profit[i] / weight[i];
}
for (i = 0; i < num; i++)
{
for (j = i + 1; j < num; j++)
{
if (ratio[i] < ratio[j])
{
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;
temp=weight[j];
weight[j] = weight[i];
weight[i] = temp;
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}
knapsack(num, weight, profit, capacity);
getch();
}

 OUTPUT



























Posted by No comments:

DAA Lab program to perform radix sort

DAA LAB Program 7

Write a program to perform radix sort.

#include<stdio.h>
#include<conio.h>
radix_sort(int array[], int n);
void main()
{
int array[100],n,i;
clrscr();
printf("\t\t\tRadix Sort\n\n\n\n");
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
printf("\nEnter the elements to be sorted: \n");
for(i = 0 ; i < n ; i++ )
{
printf("\tArray[%d] = ",i);
scanf("%d",&array[i]);
}
printf("\nArray Before Radix Sort:");  //Array Before Radix Sort
for(i = 0; i < n; i++)
{
printf("%8d", array[i]);
}
printf("\n");
radix_sort(array,n);
printf("\nArray After Radix Sort: ");  //Array After Radix Sort
for(i = 0; i < n; i++)
{
printf("%8d", array[i]);
}
printf("\n");
getch();
}
radix_sort(int arr[], int n)
{
int bucket[10][5],buck[10],b[10];
int i,j,k,l,num,div,large,passes;
div=1;
num=0;
large=arr[0];
for(i=0 ; i<n ; i++)
{
if(arr[i] > large)
{
large = arr[i];
}
while(large > 0)
{
num++;
large = large/10;
}

for(passes=0 ; passes<num ; passes++)
{
for(k=0 ; k<10 ; k++)
{
buck[k] = 0;
}
for(i=0 ; i<n  ;i++)
{
l = ((arr[i]/div)%10);
bucket[l][buck[l]++] = arr[i];
}
i=0;
for(k=0 ; k<10 ; k++)
{
for(j=0 ; j<buck[k] ; j++)
{
arr[i++] = bucket[k][j];
}
}
div*=10;
}
}
return 0;
}



OUTPUT 












Posted by No comments:
Subscribe to: Posts (Atom)