You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.
Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.
Example 1:
Input: equations = ["a==b","b!=a"]Output: falseExplanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.
Example 2:
Input: equations = ["b==a","a==b"]Output: trueExplanation: We could assign a = 1 and b = 1 to satisfy both equations.
Constraints:
1 <= equations.length <= 500equations[i].length == 4equations[i][0]is a lowercase letter.equations[i][1]is either'='or'!'.equations[i][2]is'='.equations[i][3]is a lowercase letter.
Solution:
We will make DSU and the parent array will have a size of 26 as of the English characters. If the current equation is of '==' then we will merge the two character else we will check in the next loop whether both the character has the same leader or parent. See the code for a better understanding.
5 Comments
/******************************************************************************
ReplyDeleteOnline C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include
using namespace std;
int main() {
vector orderofreq ;
int pos;
int mx=INT_MAX;
vector::iterator nextreq ;
int totalheadmov = 0;
int currhead;
cout<<"Current Head Position : ";
cin>>currhead; // Position of current head
cout<<"No of requests in queue : ";
int n;
cin>>n; //No of requests
for(int i = 0; i < n; i++)
{
cin>>pos;
orderofreq.push_back(pos);
}
while(n--)
{
for(auto it = orderofreq.begin(); it != orderofreq.end(); it++)
{
if(abs(*it-currhead)<mx)
{nextreq = it;
mx=abs(*it-currhead);
}
}
totalheadmov = totalheadmov + abs(*nextreq-currhead);
cout<<*nextreq<<" ";
currhead = *nextreq;
mx=INT_MAX;
orderofreq.erase(nextreq);
}
cout<<"Total Head Movement : "<<totalheadmov;
return 0;
}
/******************************************************************************
ReplyDeleteOnline C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
// Online C++ compiler to run C++ program online
#include
using namespace std;
int main() {
vector orderofreq ;
int pos;
int totalseektime = 0;
int currhead;
cout<<"Current Head Position : ";
cin>>currhead; // Position of current head
cout<<"No of requests in queue : ";
int n;
cin>>n; //No of requests
for(int i = 0; i < n; i++)
{
cin>>pos;
orderofreq.push_back(pos);
}
for(auto it: orderofreq)
{
totalseektime = totalseektime + abs(it-currhead);
currhead = it;
}
cout<<"Total Seek Time is : "<<totalseektime;
return 0;
}
/******************************************************************************
ReplyDeleteOnline C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include
using namespace std;
int main() {
vector orderofreq ;
int pos;
int totalheadmov = 0;
int currhead;
cout<<"Current Head Position : ";
cin>>currhead; // Position of current head
cout<<"No of requests in queue : ";
int n;
cin>>n; //No of requests
for(int i = 0; i < n; i++)
{
cin>>pos;
orderofreq.push_back(pos);
}
sort(orderofreq.begin(),orderofreq.end());
vector::iterator itr;
for(auto it = orderofreq.begin(); it != orderofreq.end(); it++)
{
if(currhead>*it)
{
itr = it;
break;
}
}
for(auto it = itr; it != orderofreq.end(); it++)
{
totalheadmov += *it - currhead;
currhead = *it;
}
itr--;
for(auto it = itr; it != orderofreq.begin(); it--)
{
totalheadmov += abs(*it - currhead);
currhead = *it;
}
cout<<"Total Head Movement is : "<<totalheadmov;
return 0;
}
//C-Scan
ReplyDelete#include
using namespace std;
int main() {
int rwarm,n,nextarm,rwarmpos;
int totalheadmov = 0;
cout<<"Enter the position of read/write arm :";
cin>>rwarm;
rwarmpos = rwarm;
cout<<"Enter the number of requests : ";
cin>>n;
vector req;
for(int i = 0; i < n; i++)
{cin>>nextarm;
req.push_back(nextarm);
}
nextarm = rwarm;
sort(req.begin(),req.end());
auto itr = req.begin();
for(auto it = req.begin(); it != req.end(); it++)
{
if(rwarm<*it)
{
itr = it;
break;
}
}
for(auto it = itr; it != req.end(); it++)
{
nextarm = *it;
totalheadmov = totalheadmov + (nextarm - rwarm);
rwarm = nextarm;
}
if(nextarm < 199) totalheadmov += (199 - nextarm);
totalheadmov += 199;
rwarm = 0;
nextarm = req[0];
int it = 0;
while(nextarm < rwarmpos)
{
totalheadmov += nextarm - rwarm;
rwarm = nextarm;
nextarm = req[++it];
}
cout<<endl<<"Total head Movement : "<<totalheadmov;
return 0;
}
//SCAN
ReplyDelete#include
using namespace std;
int main() {
int rwarm,n,nextarm,rwarmpos;
int totalheadmov = 0;
cout<<"Enter the position of read/write arm :";
cin>>rwarm;
rwarmpos = rwarm;
cout<<"Enter the number of requests : ";
cin>>n;
vector req;
for(int i = 0; i < n; i++)
{cin>>nextarm;
req.push_back(nextarm);
}
nextarm = rwarm;
sort(req.begin(),req.end());
auto itr = req.begin();
for(auto it = req.begin(); it != req.end(); it++)
{
if(rwarm<*it)
{
itr = it;
break;
}
}
for(auto it = itr; it != req.end(); it++)
{
nextarm = *it;
totalheadmov = totalheadmov + (nextarm - rwarm);
rwarm = nextarm;
}
if(nextarm < 199) totalheadmov += (199 - nextarm);
totalheadmov += 199 - req[0];
cout<<endl<<"Total head Movement : "<<totalheadmov;
return 0;
}
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.