CareerCup

I think O(logn) will be the answer b/c if no is present it will be at middle pos.Now we hv to count how many times it occurs in array (for that find first occurance and last occurance using binary search in O(logn) time ) if it is more than n/2 then this is the number.so time is O(1) + O(logn) ie O(logn)

ur code doesnt work for all 9 case.
eg for 999 ur code gives 1019

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int isNum(char ch)
{
if(ch>=48 && ch<=57)
return 1;
else
return 0;
}

int StrToNum(char s[],int strt,int end)
{
int i,tmp,res=0;
for(i=strt;i<=end;i++)
{
tmp=s[i]-'0';
res = res*10+tmp;
}
return res;
}

int main()
{
int p,q,ctr,i,x;
char ch,str[105];
//char ch,str[105]="a1b12c3d11e5g2";
cin>>str;
for(i=0;i<strlen(str);i++)
{
if(isNum(str[i]))
{
ch=str[i-1];
p=i;
while(isNum(str[i]))
i++;
q=i-1;
ctr = StrToNum(str,p,q);
for(x=1;x<=ctr;x++)
cout<<ch;
i--;
}
}
return 0;
}

//showing Runtime error Plz help?????

#include<iostream>
#include<stdio.h>
using namespace std;

struct StackNode
{
int data;
struct StackNode *next;
};

int isEmpty(struct StackNode *root)
{
return (root== NULL);
}

struct StackNode * newNode(int data)
{
struct StackNode *newNode = (struct StackNode *)malloc(sizeof(struct StackNode));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void push(struct StackNode **root,int data)
{
struct StackNode *stack = newNode(data);
stack->next = *root;
*root = stack;
printf("%d pushed to stack\n",data);
}

int pop(struct StackNode **root)
{
if(isEmpty(*root))
return INT_MIN;
struct StackNode *tmp =*root;
int vl=tmp->data;
*root = (*root)->next; //OR *root = tmp-next;
free(tmp);
return vl;
}

int peek(struct StackNode *root)
{
if(isEmpty(root))
return INT_MIN;
return (root->data);
}

struct StackNode* SortTheStack(struct StackNode *S)
{
struct StackNode *r;
int tmp;
while(!isEmpty(S))
{
tmp = pop(&S);
while(!isEmpty(r) && peek(r)>tmp)
{
push(&S,pop(&r));
}
push(&r,tmp);
}
return r;
}

int main()
{
struct StackNode *S = NULL;
struct StackNode *r = NULL;
push(&S,40);
push(&S,20);
push(&S,10);
push(&S,30);
r = SortTheStack(S);
printf("sorted stack is: ");
while(!isEmpty(r))
{
printf("%d ",pop(&r));
}
return 0;
}

int getIndex(int arr[],int num)
{ int low=0,high=1;
if(arr[low] == num)
return low;
else if(arr[high] == num)
return high;
while(arr[high]<num && high<INT_MAX+1)
{ high=high*2; }
low=high/2;
int pos=binarysearch(arr,low,high,num); //general binary search
return pos;
}

int main()
{
int *arr=new int[1000];
int i,k;
for(i=0;i<1000;i++)
arr[i]=i*i;
cout<<"enter no to be searched:\n";
cin>>k;
int indexvl=getIndex(arr,k);
cout<<indexvl<<endl;
return 0;
}