# American Express OA

In the graph problem i was getting TLE for four test cases when i was calculating number of prime factors in O(sqrt(n)) . The trick was to use modified sieve which stores the smallest prime factor of each number. This takes O(log(n)) time to calculate number of factors. I then stored the number of factors and node in a vector of pair and sorted them as per the conditions.( to this i had to store the distance of each node from root ) . Then i stored answer for each value from 1 to 10^6 because number of queries were almost comparable to the range of n . So my algorithm took O(log(X)) time for each query. Would like to know if anyone had a different or better approach? Note- Only consider three alpabhets a ,b ,c
A string is called diverse if no 3 consecutive letters are same. In other words diverse string may not contain any of the strings “aaa”,“bbb”,“ccc”

Given three integers x,y,z write a function to return any longest possible diverse string containing at most x letters ‘a’, y letters ‘b’,z letters ‘c’.
If no possiblity of building any string return empty string

example1
x=8 ,y=1, z=1
then function may return aabaacaa or aacaabaa
example 2
x=1,y=3,z=1
then function may return abbcb

z,y,z in range 1 to 100

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
int a;cin>>a;
int b;cin>>b;
int c;cin>>c;
priority_queue<pair<int,char>> pq;
if(a!=0){pq.push({a,'a'});}
if(b!=0){pq.push({b,'b'});}
if(c!=0){pq.push({c,'c'});}
char temp='?';
string res="";
while(!pq.empty())
{

auto p1=pq.top();pq.pop();
if(p1.second==temp)
{
cout<<p1.second<<endl;
if(!pq.empty())
{
auto p2=pq.top();
pq.push(p1);
p1=p2;
}else{
break;
}
}
if(p1.first>=2)
{
res+=p1.second;
res+=p1.second;
p1.first=p1.first-2;
cout<<p1.second<<endl;
}
else if(p1.first==1)
{
res+=p1.second;
p1.first=p1.first-1;
}
if(!pq.empty())
{
auto p3=pq.top();
pq.pop();
res+=p3.second;
p3.first=p3.first-1;
temp=p3.second;
if(p3.first>0)
{
pq.push(p3);
}
if(p1.first>0){pq.push(p1);}
cout<<p3.second<<endl;
}
else
{
break;
}

}
cout<<res;
}

``````