Posts

Showing posts with the label C

SPOJ - TRICOUNT

Problem Code : TRICOUNT Problem : Counting Triangles Platform : SPOJ Language : C Link : SPOJ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 //submitted //http://www.spoj.com/problems/TRICOUNT/ #include<stdio.h> int main () { int t; scanf( "%d" , & t); while (t -- ) { long long unsigned num,sum; scanf( "%llu" , & num); if (num % 2 == 0 ) sum = (num * (num + 2 ) * (( 2 * num) + 1 )) / 8 ; else sum = ((num * (num + 2 ) * (( 2 * num) + 1 )) - 1 ) / 8 ; printf( "%llu \n " ,sum); } return 0 ; }

Post Order Traversal In Binary Tree

Image
Post Order Traversal In Binary Tree Its LRN ordered traversal. The order goes this way: L: Traverse the left sub tree. R: Traverse the right sub tree. N: visit the node Lets check with an example. Consider the following example. Traverse the left sub tree of node 1 Traverse the left sub tree of node 2 Visit the node 4 Traverse the right sub tree of node 2 Visit the node 5 Visit the node 2 Traverse the right sub tree of node 1 Traverse the left subtree of node 3 Visit the node 6 Traverse the right sub tree of node 3 Visit the node 7 Visit the node 3 Visit the node 1 On completing the traversal we get the post order if we follow the bolded nodes. Post Order: 4 , 5 , 2 , 6 , 7 , 3 , 1

In Order Traversal In Binary Tree

Image
In Order Traversal In Binary Tree Its LNR ordered traversal. The order goes this way: L: Traverse the left sub tree. N: visit the node R: Traverse the right sub tree. Lets check with an example. Consider the following example. Traverse the left sub tree of node 1 Traverse the left sub tree of node 2 Visit the node 4 Visit the node 2 Traverse the right sub tree of node 2 Visit the node 5 Visit the node 1 Traverse the right sub tree of node 1 Traverse the left subtree of node 3 Visit the node 6 Visit the node 3 Traverse the right sub tree of node 3 Visit the node 7 On completing the traversal we get the in order if we follow the bolded nodes. In Order: 4 , 2 , 5 , 1 , 6 , 3 , 7

Pre Order Traversal In Binary Tree

Image
Pre Order Traversal In Binary Tree Its NLR ordered traversal. The order goes this way: N: visit the node L: Traverse the left sub tree. R: Traverse the right sub tree. Lets check with an example. Consider the following example. Visit the node 1 Traverse the left sub tree of node 1 Visit the node 2 Traverse the left sub tree of node 2 Visit the node 4 Traverse the right sub tree of node 2 Visit the node 5 Traverse the right sub tree of node 1 Visit the node 3 Traverse the left subtree of node 3 Visit the node 6 Traverse the right sub tree of node 3 Visit the node 7 On completing the traversal we get the pre order if we follow the bolded nodes. Pre Order: 1 , 2 , 4 , 5 , 3 , 6 , 7

Traversal In A Binary Tree - Tree -3

Image
Traversal In Binary Tree Traversing a binary tree means visiting each node of the tree exactly once. At each node : N : Visit the node L : Traverse its left subtree R : Traverse its right subtree These actions can be performed in any order... (3! = 6 different ways of ordering the three tasks.) Different orders: NRL NLR LNR LRN RNL RLN But we follow the convention which states left subtree to be traversed before right sub tree. Thus we are left with three orders: NLR , LNR and LRN The orders are named according the position of the node i.e., position of N in the order. pre : NLR in  : LNR post : LRN PRE ORDER TRAVERSAL: ( NLR ) N : Visit the node L : Traverse the left subtree R : Traverse the right subtree IN ORDER TRAVERSAL: ( LNR ) L : Traverse the left subtree N : Visit the node R : Traverse the right subtree ...

Tree data structure - 2

Image
Trees - 2 Types: Strictly binary tree: Degree is every node either 0 or 2. Full Binary tree: Degree of every node is 2. Complete Binary Tree:A binary tree in which every level , exccept possibly the last , is completely filled and all nodes are as far left as possible. Array Representation of binary tree: Also called as sequential representation or linear representation We use 1D array Store the data with indexed 1 i.e., root node at Array[1](Even we can use 0 based index ) If a node is at index k in the array, its left child is at index 2k and right child at index 2k+1. If a node at index k then its parent is at index floor(k/2) The size of array needed to store a tree of height h is 2 h -1 Linked list representation : struct node { struct node *left; struct node *right; int data; } This structure can be used for the binary tree. Self referential structure where first and second...

Tree Data Structure - I

Image
Trees The data is organised in a hierarchial manner. Terminology: Node Edges Parent Node Child Node Leaf Node Level Height Siblings Path There exists only one path between any two nodes Ancestor: Any node z is ancestor of x if z lies in the path between root node and x Descedant: Nodes which are not ancestors to x are the descendant to x. Subtree: The root of subtree is usually used to name that subtree Degree Forest Definition of a tree Binary Tree An empty tree can be a binary tree Similar trees: If same struture Copies: Same struccture and same contents Properties: Max no of nodes on any level x is 2 x Max no of nodes in a tree with a heoght h is 2 h -1 The minimum number of nodes possible in a binary tree of height h is h. If a binary tree contains n nodes, then its maximum heoght possible is log 2 (n+1) Total number of nodes= total no of edges+1 Strictly Binary T...

CODECHEF - ACT2

Problem Code : ATC2 Problem : Harry And N-th Number Platform : Codechef Type : Online Language : C Link : CODECHEF //submitted //https://www.codechef.com/CODH2018/problems/ATC2 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> void func(long long int arr[]) { int n; scanf("%d",&n); printf("%lld\n",arr[n]); return; } int main() { int cases; scanf("%d",&cases); long long int *arr; arr=(long long int *)malloc(700005*sizeof(long long int)); long long int i; arr[1]=1; for(i=2;i<700002;i++) { arr[i]=arr[i-1]+sqrt(i); } while(cases--) { func(arr); } return 0; }

CODECHEF - L56GAME

Problem Code : L56GAME Problem : Chef and Game with Sequence Platform : Codechef Type : Lunch Time Language : C Link : CODECHEF 1: //working 2: //no option to submit 3: //https://www.codechef.com/LTIME56/problems/L56GAME 4: #include <stdio.h> 5: #include <string.h> 6: #include <stdlib.h> 7: void func() 8: { 9: int n; 10: scanf("%d",&n); 11: int i; 12: int odd=0; 13: int even=0,temp; 14: for(i=0;i<n;i++) 15: { 16: scanf("%d",&temp); 17: if(temp%2==0) 18: { 19: even++; 20: } 21: else 22: { 23: odd++; 24: } 25: } 26: int ans=0; 27: ans=ans+ (odd%2); 28: even = even+ (odd/2); 29: if(even>0) 30: { 31: ans++; 32: } 33: pri...

CODECHEF - RECTANGL

Problem Code : RECTANGL Problem : Rectangle Platform : Codechef Type : Online Language : C Link : CODECHEF 1: //submitted 2: //https://www.codechef.com/JAN18/problems/RECTANGL 3: #include <stdio.h> 4: void func() 5: { 6: int arr[4]; 7: scanf("%d",&arr[0]); 8: scanf("%d",&arr[1]); 9: scanf("%d",&arr[2]); 10: scanf("%d",&arr[3]); 11: int i,j,temp; 12: for(i=0;i<=2;i++) 13: { 14: for(j=0;j<=2-i;j++) 15: { 16: if(arr[j]<arr[j+1]) 17: { 18: temp=arr[j]; 19: arr[j]=arr[j+1]; 20: arr[j+1]=temp; 21: } 22: } 23: } 24: //printf("%d-%d-%d-%d--\n",arr[0],arr[1],arr[2],arr[3]); 25: if(arr[0]==arr[1] && arr[2]==ar...

CODECHEF - CIELAB

Problem Code : CIELAB Problem : Ciel and A-B Problem Platform : Codechef Language : C Level : Easy Link : CODECHEF 1: //submitted 2: //https://www.codechef.com/problems/CIELAB 3: #include <stdio.h> 4: #include<stdlib.h> 5: #include <string.h> 6: void func() 7: { 8: int a,b; 9: scanf("%d",&a); 10: scanf("%d",&b); 11: int ans=a-b; 12: //for +1 13: if((ans+1)%10!=0) 14: { 15: printf("%d\n",ans+1 ); 16: return; 17: } 18: //for -1 19: printf("%d\n",ans-1 ); 20: } 21: int main() 22: { 23: int cases=1; 24: // scanf("%d",&cases); 25: while(cases--) 26: { 27: func(); 28: } 29: return 0; 30: }

CODECHEF - MAXSC

Problem Code : MAXSC Problem : Maximum Score Platform : Codechef Language : C Link : CODECHEF //submitted https://www.codechef.com/JAN18/problems/MAXSC #include <stdio.h> #include <stdlib.h> void func() { int n; scanf("%d",&n); int **arr; arr=(int **)malloc(sizeof(int*)*n); int i,j; for(i=0;i<n;i++) { arr[i]=(int*)malloc(sizeof(int)*n); } for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&arr[i][j]); } } /*for(i=0;i<n;i++) { for(j=0;j<n;j++) { printf("%d ",arr[i][j]); } printf("\n"); }*/ long long int sum=0; int maxasofnow=1000000001; int flag=1; int localmax=-1; for(i=n-1;i...