Category: Programming Problem

Tree construction from Inorder & Preorder [ Microsoft ]

Posted By: Asif NaeemPosted On:

Problem: Provided Inorder and PreOrder of a tree. Construct the tree and print it in PostOrder traversal. #include <stdio.h> #include <iostream> #include <string.h> #include<stdlib.h> #include <string> using namespace std; int preOrderIdx=0; struct Node{ int data; Node *left; Node *rit; }; int search(int in[],int in_stIndex,int in_endIndex,int data) { for(int i=in_stIndex;i<=in_endIndex;i++) { if(in[i]==data) return i; } }

Continue Reading “Tree construction from Inorder & Preorder [ Microsoft ]” →

Karatsuba’s Fast Multiplication Algorithm

Posted By: Asif NaeemPosted On:

Problem: Find  multiplication result of two large numbers in less than O(n^2) time complexity. #include <iostream> #include <string> /* 123456 34343 add=157799 sub=0@J113 */ using namespace std; void makeEqualString(string &a,string &b) { if(a.size()==b.size()) return; else { if(a.size()>b.size()) { for(int i=1;i<=a.size()-b.size();i++) b='0'+b; } else { for(int i=1;i<=b.size()-a.size();i++) a='0'+a; } } } string addString(string a,string b) {

Continue Reading “Karatsuba’s Fast Multiplication Algorithm” →

Almost Prime number

Posted By: Asif NaeemPosted On:

Problem:A no is said to be  k-Almost Prime Number if it  has exactly k prime factors (not necessary distinct). Your task is to complete the functionprintKAlmostPrimes which takes two argument k and N and prints the  first N numbers that are k prime. Problem Link /*You are required to complete this function*/ bool isPrime(int n) { bool arr[20]; int i; arr[2]=1;arr[3]=1;arr[5]=1;arr[7]=1; arr[11]=1;arr[13]=1;arr[17]=1;arr[19]=1;

Continue Reading “Almost Prime number” →

10166

Posted By: Asif NaeemPosted On:

#include <iostream> #include <algorithm> #include <queue> #include <cstdio> #include <cstring> #include <string> #include <map> #include <vector> using namespace std; struct Schedule{ int to; int start,end; Schedule(int a,int b,int c) { to = a; start = b; end = c; } }; vector<Schedule> vb[101]; int kase=1; map<string,int> mp; char dest_city[1024], start_city[1024]; int earliest_start_time, cityNum; int dist[2400][101];//saves

Continue Reading “10166” →

10039

Posted By: Asif NaeemPosted On:

#include <iostream> #include <algorithm> #include <queue> #include <cstdio> #include <cstring> #include <string> #include <map> #include <vector> using namespace std; struct Schedule{ int to; int start,end; Schedule(int a,int b,int c) { to = a; start = b; end = c; } }; vector<Schedule> vb[101]; int kase=1; map<string,int> mp; char dest_city[1024], start_city[1024]; int earliest_start_time, cityNum; int dist[2400][101];//saves

Continue Reading “10039” →

10170

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> #define ul unsigned long long//double//long long using namespace std; int main() { ul s,d,a,b; ul subtract; ul lw,hi,mid,res; while(scanf("%llu%llu",&s,&d)!=EOF) { if(d<=s) { printf("%llu\n",s); continue; } subtract=(s*(s-1))/2; lw=s; hi=s+d/s; res=-1; while(hi-lw>1) { mid=(lw+hi)/2; if(((mid*(mid+1))/2-subtract) <d) lw=mid+1; else if(((mid*(mid+1))/2-subtract)>d) hi=mid; else if(((mid*(mid+1))/2-subtract)==d) { res=mid; break; } } if(res!=-1) printf("%llu\n",res); else { //cout<<lw<<" "<<hi<<"\n";

Continue Reading “10170” →

974

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #define ll long long using namespace std; ll arr[40001]; vector<int> vb; ll _pow(int pwr) { if(pwr==0) return 1; else return 10*_pow(pwr-1); } bool Isfunc(ll a,int b) { int tmp; tmp=a; int pwr=0; int num=0; while(tmp) { num=num + (tmp%10)*_pow(pwr); tmp/=10; if(tmp+num==b && tmp!=0 && num!=0)

Continue Reading “974” →

696

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> using namespace std; int main() { int r,c,tmp,res; int row,col; //FILE *fp; //fp=fopen("out.txt","w"); while(scanf("%d%d",&r,&c)) { if(r+c==0) break; if((r==1 || c==1) || r==0 || c==0) { printf("%d knights may be placed on a %d row %d column board.\n",r*c,r,c); //fprintf(fp,"%d knights may be placed on a %d row %d column board.\n",r*c,r,c); continue; }

Continue Reading “696” →

661

Posted By: Asif NaeemPosted On:

#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; int capacity[21]; bool isTurnOn[21]; int main() { int n,m,c; int MX=0; int device; int kase=1; bool IsFUSE; long long total; while(scanf("%d%d%d",&n,&m,&c)) { if(n+m+c==0) break; //memset(capacity,0,sizeof(capacity)); //memset(isTurnOn,0,sizeof(isTurnOn)); IsFUSE=0; for(int i=1;i<=n;i++) { scanf("%d",&capacity[i]); isTurnOn[i]=0; } total=0; MX=0; for(int i=1;i<=m;i++) { scanf("%d",&device); if(IsFUSE) continue; if(isTurnOn[device]==0) { isTurnOn[device]=1;

Continue Reading “661” →