pratikrd
BAN USERAlgo:
1. During the first scan create a hashmap for all elements storing the count of the key.
2. Now during the next scan consider only those elements whose hash[key] ==1 (Meaning key present only once in the input.) and find the desired element based on the index.
Algorithm
1. Read the characters
a. Opening brackets : push in the stack and go to step 1
b. operator: push in the stack and go to step 1
c. number: print
d. closing brackets: pop from stack
i. if it is a closing bracket - ignore
ii. if it is an operator - print
e. new line - exit
public int maxHeight(BinaryTree b)
{
if(b==null) return 0;
return 1 + Math.max(maxHeight(b.left), maxHeight(b.right));
}
public void maxPath(BinaryTree b,int[] a,int index)
{
if(b==null)
{
for(int i = 0; i < index;i++)
System.out.println(a[i] + "");
return;
}
a[index] = b.data;
index++;
if(maxHeight(b.left) > maxHeight(b.right))
maxPath(b.left, a, index);
else maxPath(b.right, a, index);
}
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
cin >> s;
int i,j;
for (i=0; i<s.size();i++)
{
if(s[i] == '1')
break;
}
for (j = s.size();j>=0;j--)
{
if(s[j] == '0')
break;
}
cout << endl << j-i << endl;
cin.get();
cin.get();
return 0;
}
If the arrays are not sorted, the best sorting algo will take O(nlogn) time. and then the linear scan approach posted by venkatesh will work. In all it will take O(nlogn) only.
- pratikrd July 26, 2013