hugakkahuga
BAN USER- 3of 13 votes
AnswersIn a language, there are only 4 characters ‘h’, ‘i’,’r’, ‘e’. and we have to write a function which takes a string as input and returns whether the given input string is a “valid word” or not.
- hugakkahuga in India
Definition of valid word :
1. A given word is a valid word if it is of the form h^n i^n r^n e^n where n >=1. (eg: hhiirree)
2. Valid words has concatenation property i.e. if w1 and w2 are valid words w1w2 is also a valid word.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
#include<vector>
#include<iostream>
using namespace std;
void decimal(int rem, int divisor);
int main() {
int n,d;
cin>>n>>d;
cout<<n/d<<".";
decimal(n%d,d);
}
void decimal(int rem, int divisor) {
vector<int> hash(divisor,-1);
vector<int> decimal;
while(hash[rem]==-1) {
decimal.push_back((rem*10)/divisor);
hash[rem]=decimal.size()-1;
rem=(rem*10)%divisor;
}
for(int i=0;i<hash[rem];i++)
cout<<decimal[i];
cout<<"(";
for(int i=hash[rem];i<decimal.size();i++) {
cout<<decimal[i];
}
cout<<")"<<endl;
}
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
void backtrack(string& a, const string& sorted, string& result, int s, int p);
int main() {
string a;
cin>>a;
string sorted;
vector<int> count(10,0);
for(int i=0;i<a.size();i++) {
count[a[i]-'0']++;
}
int k=0;
for(int i=9;i>=0;i--) {
sorted.append(count[i],'0'+i);
}
string result="";
int s;
cin>>s;
backtrack(a,sorted,result,s,0);
cout<<result<<endl;
}
void backtrack(string& a, const string& sorted, string& result, int s, int p) {
if(s==0 || p>=a.size()) {
result = max(result,a);
}
else if(sorted[p]==a[p]) {
backtrack(a,sorted,result,s,p+1);
}
else {
for(int i=p+1;i<a.size();i++) {
if(a[i]==sorted[p]) {
swap(a[p],a[i]);
backtrack(a,sorted,result,s-1,p+1);
swap(a[p],a[i]);
}
}
}
}
#include<stdio.h>
void convert(int a[], int n);
int main() {
int a[] = {1,2,3,4,5,6,7,8};
convert(a,sizeof(a)/sizeof(int));
}
void convert(int a[], int n) {
int left=a[0];
a[0]=0;
for(int i=1;i<n;i++) {
int temp=a[i];
a[i]=left;
left+=temp;
}
int sum=left, right=0;
for(int i=n-1;i>=1;i--) {
int temp=sum-a[i];
sum=a[i];
a[i]+=right;
right+=temp;
}
a[0]+=right;
for(int i=0;i<n;i++) {
printf("%d ",a[i]);
}
printf("\n");
}
#include<stdio.h>
void backtrack(int[][4], int, int) ;
int main() {
int a[4][4];
backtrack(a,0,0);
}
void backtrack(int a[][4], int i, int j) {
if(i==4) {
printf("\n");
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
printf("%d ",a[i][j]);
}
printf("\n");
}
}
for(int k=1;k<=4;k++) {
int x;
for(x=0;x<i && a[x][j]!=k;x++);
if(x<i)
continue;
for(x=0;x<j && a[i][x]!=k;x++);
if(x<j)
continue;
if(i%2) {
if(j%2) {
if(a[i-1][j-1]==k)
continue;
}
else {
if(a[i-1][j+1]==k)
continue;
}
}
a[i][j]=k;
backtrack(a,j==3?i+1:i,(j+1)%4);
}
}
it was an algorithm question....pseudo code/c/c++
- hugakkahuga October 23, 2013Really elegant solution !!
- hugakkahuga September 28, 2013#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main() {
char num[]="19999";
char digits[]="12999";
int dc[10];
int n=5;
char res[6];
int i,j,k;
memset(dc,0,sizeof(dc));
for(i=0;i<n;i++) {
dc[digits[i]-'0']++;
}
for(i=0;i<n;i++) {
for(j=num[i]-'0';j<=9;j++) {
if(dc[j]>0) {
dc[j]--;
res[i]=j+'0';
break;
}
}
if(j!=num[i]-'0')
break;
}
if(j==10) {
for(i--;i>=0;i--) {
dc[res[i]-'0']++;
for(j=res[i]-'0'+1;j<=9;j++) {
if(dc[j]>0) {
dc[j]--;
res[i]=j+'0';
break;
}
}
if(j<=9)
break;
}
}
if(i==-1 || i==n) {
printf("no such number\n");
return 0;
}
for(k=0;k<=9 && i<n;k++) {
for(j=0;j<dc[k];j++) {
res[++i]=k+'0';
}
}
res[n]='\0';
printf("%s\n",res);
return 0;
}
There is one little mistake in your code. Try the string "BCDEBCDBCC"
Below is the corrected code.
#include<iostream>
#include<string>
std::string lex_min(const std::string&);
int main() {
std::cout<<lex_min("BCDEBCDBCC");
return 0;
}
std::string lex_min(const std::string& str) {
int size = str.size();
std::string input = str + str;
int offset = 0;
int answer = -1;
for (int i = 0; i < size * 2; i++) {
if (answer == -1)
{
// First character
answer = i;
}
else if (input[i] < input[answer]) {
// We definitely have a new answer here
answer = i;
// Reset the offset for future tie
offset = 0;
}
else if (input[i] == input[answer + offset]) {
// We might have another answer here
// move the offset forward
offset++;
}
else if (input[i] < input[answer + offset]) {
// we have found something even better
// than what we had before
// Set marker for new answer
answer = i - offset;
offset = 0;
if(input[i] == input[answer]) /* THIS IS THE CORRECTION*/
offset=1;
}
else {
offset = 0;
}
}
return input.substr(answer, size);
}
I forgot to mention the base cases which will be : For n = 1 to 7, A(n) = n
- hugakkahuga July 28, 2013I forgot to mention the base cases which will be : For n = 1 to 7, A(n) = n
- hugakkahuga July 28, 2013
- hugakkahuga January 17, 2015