Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
This one is reporting correct results ! Can you elaborate more on the logic used ? it's not easy to trace what you're doing.
During preprocessing, i am calculating two matrices, lets say 'a' and 'b'. In array 'a', a[i][j] stores number of valid combinations of length i+1 starting from (j+1)th character. e.g. first row in Matrix 'a' will contain all 1s as there is only valid combination of length 1 starting from a,b,c...z. For calculating a[1][0], we need all valid combinations of lenth 2 starting from from character 'a' and it is equivalent to valid combinations of length 1 starting from character b,c,..z. So,a[1][0]=a[0][1]+a[0][2]+...+a[0][25].
Now, b[i][j] represents index of first valid combination of length i+1 starting from (j+1)th character. b[i][j] can be calculated by taking sum of prev elem of array 'a' and array 'b'. i.e. b[i][j] = a[i][j-1] + b[i][j-1]
After calculating array b, we just need to calculate index of desired string from array 'b'
I am bad at explaining things in writing.. Let me know if more explanation is needed on this
The total words is 2^26 -1.
For a given word, the word with small size occur first.
Let n be the length of the word,
Total number of words with size less than n is C(26, 1) + C(26, 2) + ...+ C(26, n -1)
Then calculate how many words with the same size prior to the given word
the sum of two numbers plusing one is the index
sites.google.com/site/spaceofjameschen/annnocements/printtheindexofawordwithlettersinascendingorder--microsoft
Perfect James ! I was missing the part where you're 'z'-j C str.len - i -1 this is exactly what I needed.
Thanks and +1 for that answer.
For calculation of aez:
Get yz value . It is equal to 26 + 25 + .... + 1 = 351
abc = yz + 1 = 352
acd = abc + 23 + 1 = 376
ade = acd + 22 + 1 = 399
aef = ade + 21 + 1 = 421
Finally aez = aef + 20 = 421 + 20 = 441
Nice approach, but could you please devise an algorithm? For ex: how would you compute the value of 'acegi'?
The total words is 2^26 -1.
For a given word, the word with small size occur first.
Let n be the length of the word,
Total number of words with size less than n is C(26, 1) + C(26, 2) + ...+ C(26, n -1)
Then calculate how many words with the same size prior to the given word
the sum of two numbers plusing one is the index
sites.google.com/site/spaceofjameschen/annnocements/printtheindexofawordwithlettersinascendingorder--microsoft
ab ----> 27
--------------------------------
ba ----> 0
--------------------------------
bc ----> 52
--------------------------------
aez ----> 441
--------------------------------
cde ----> 928
--------------------------------
cdb ----> 0
--------------------------------
cdf ----> 929
--------------------------------
The output is correct
moqx ----> 16983
--------------------------------
xyz ----> 2951
--------------------------------
hjmoqsu ----> 930152
public class SeqTONum {
private final static int ALPHABETNUM = 26;
public static int GetSequenceNum(int numberOfChars, String input)
{
char[] arrInput = input.toUpperCase().toCharArray();
/*
* Test some illegal situations
* Return 0 if illegal
*/
if (numberOfChars <=0 || numberOfChars > 26)
return 0;
if (arrInput.length > numberOfChars)
{
return 0;
}
if (arrInput.length > 1){
for (int i = 0; i < arrInput.length-2; i++){
if(arrInput[i]>=arrInput[i+1])
return 0;
}
}
/*
* Seq to Num
*/
int num = 0;
if( arrInput.length == 1){
num +=(int)arrInput[0] - ((int) 'A') + 1;
return num;
}
for(int i = 0; i < arrInput.length -1 ; i++){
num += comNum(ALPHABETNUM, i + 1);
}
for(int i = 0; i < arrInput.length; i++) {
if(i==0){
for(char first = 'A'; first < arrInput[0]; first = (char)(first + 1)){
int bit = arrInput.length - 1;
int left = 'Z' - first;
num += comNum(left, bit);
}
} else if(i == arrInput.length-1){
num += (arrInput[i]-arrInput[i-1]);
} else{
for(char cur = (char)(arrInput[i-1] + 1); cur < arrInput[i]; cur = (char)(cur + 1)){
int bit = arrInput.length - i - 1;
int left = 'Z' - cur;
num += comNum(left, bit);
}
}
}
return num;
}
public static int comNum(int num, int top){
if(top == 0)
return 0;
int value = 0;
int tmp1 = 1, tmp2 = 1;
for(int i = 0 ; i < top; i++){
tmp1 *= (num-i);
tmp2 *= (top-i);
}
value = tmp1/tmp2;
return value;
}
public static void main(String[] args){
System.out.println(GetSequenceNum(5, "vwxyz"));
}
}
I think a brute force approach for this algorithm is, given a string str, generating all values in order starting from "a", incrementing a counter, until we find the string str and return the value of the counter. So, for the example "aez", we will need to iterate 441 times.
yes but I think it could be done more optimized using combinations but couldn't get far more than 3 letters. Formula for 3 letters could look like that:
26C1 + 26C2 + [Σ(26-i) {i=2 to n2-1}] + n3 - n2
Where n1,n2 and n3 represents the index of the character in the alphabet (1->26)
So in the case of aez:
n1 = 1
n2 = 5
n3 = 26
= 26 + 325 + 24 + 23 + 22 + 26 - 5
= 441
So in case I'm in the right track, we need this formula to be more general for n characters where 2 <= n <= 26
"aez" is calculated as this:
26+(25+24+23+22+21+20+19+18+17+16+14+13+12+11+10+9+8+7+6+5+4+3+2+1+0+0) +25+24+23+22+21
modified form below:
26+25(24)/2 +25+24+23+22+21
26 + n*(n-1)/2+sum of arithmetic progression of 5(e) numbers starting from (26-e) 21
26+sum of arithmetic progression till 25 + sum of arithmetic progression of 5(e) numbers starting from (26-e) 21
I don't know if it will work for all numbers.
Lets start with reducing our problem space.
suppose there are only 5 alphabets in question here
a,b,c,d,e so it would be like
a=1
b=2
c=3
d=4
e=5
ab = 6
ac = 7
ad = 8
ae = 9.....
to find 'cde' we will do = c*5^2 + d*5^1+c - invalid combinations.(aa,ba,bb,...) etc
finding invalid combinations -
of length 2
starting with
a=1(aa)
b=2(ba,bb)
c= 3(ca,cb,cc)
d=4(da,db,dc,dd)
e =5(ea,eb,ec,ed)
-----------
length 3
a = (a-a+1)*5^(length-2)+#(b-e) invalid of length 2
b= (b-a +1)*5^(length-2)+(c-e) invalid of length 2
and so on
-----------------
length 4
a = (a-a+1)*5^(length-2)+#(b-e) in valid of length 2
---------------------------
We also need to find invalid combinations selectively like in case of cde. we need to subtract total #invalid combinations of length 2 but we need to be selective in case of length 3.
We will subtract only those invalids which start with a*, b*,ca*,cb*,cc*,cda, cdb,cdc,cdd
Yes. its better to find invalid combinations then subtract from the total.
let say sequecne goes as follows
a = 1
b = 2
c = 3...
z = 26...
aa = 27.
ab = 28...
...
aez = 832.
whatever be the string input (if it is invalid, it can be found in 1 attempt).
if it is valid get corresponding numbers as follows.
int get_number(string str)
{
int result = 0;
for(int i=0; i<str.length(); i++)
{
double local = Math.pow(26,length-1-i);
result = result + static_cast<int> (local)*(str[i]-96);
}
return result;
}
above code returns ab = 28. and aez = 832
now maths lies here.
till ab there is only one invalid combination that is aa = 1
so subtracting 1 from 28 gives 28-1 = 27 is answer for ab
now take case of aez
first find invalid combinations for 2 letter strings.
a=1(aa)
b=2(ba,bb)
c=3(ca,cb,cc)
d=4(da,db,dc,dd)
e=5(ea,eb,ec,ed,ee)
and so on...
total invalid 2 letter combinations are 1 + 2 + 3+ .......26 = 26*27/2 = 351
next find invalid combinations of three letters strings
starts with aa there are 26 invalid combinations (aaa,aab.........aaz)
starts with ab there are 2 invalid combinations (aba,abb)
starts with ac there are 3 invalid combinations (aca,acb,acc)
starts with ad there are 4 invalid combinations (ada,adb,adc,add)
starts with ae there are 5 invalid combinations (aea,aeb,aec,aed,aee)
so there are total (26+2+3+4+5) = 40 three letter invalid combinations.
so aez value = 832 - 351 (2 letter invalid combinations) - 40 (3 letter invalid combinations till aez) = 832 - 391 = 441 is answer.
but i dont know how to put this in general coding logic.
The idea is to change the string into base-26 system. The pseudo code as follows:
int sum(String str)
{
//First check the str is monotonic increasing.
if( str is not increasing ) return -1;
int sum = 0;
int length = str.length;
for(int i = 0; i < length; i++) {
//assuming all letters are in lower case.
sum += (26 ^ ( length - i - 1) ) * ( (str[i] - 'a') + 1);
}
return sum;
}
public class SeqTONum {
private final static int ALPHABETNUM = 26;
public static int GetSequenceNum(int numberOfChars, String input)
{
char[] arrInput = input.toUpperCase().toCharArray();
/*
* Test some illegal situations
* Return 0 if illegal
*/
if (numberOfChars <=0 || numberOfChars > 26)
return 0;
if (arrInput.length > numberOfChars)
{
return 0;
}
if (arrInput.length > 1){
for (int i = 0; i < arrInput.length-2; i++){
if(arrInput[i]>=arrInput[i+1])
return 0;
}
}
/*
* Seq to Num
*/
int num = 0;
if( arrInput.length == 1){
num +=(int)arrInput[0] - ((int) 'A') + 1;
return num;
}
for(int i = 0; i < arrInput.length -1 ; i++){
num += comNum(ALPHABETNUM, i + 1);
}
for(int i = 0; i < arrInput.length; i++) {
if(i==0){
for(char first = 'A'; first < arrInput[0]; first = (char)(first + 1)){
int bit = arrInput.length - 1;
int left = 'Z' - first;
num += comNum(left, bit);
}
} else if(i == arrInput.length-1){
num += (arrInput[i]-arrInput[i-1]);
} else{
for(char cur = (char)(arrInput[i-1] + 1); cur < arrInput[i]; cur = (char)(cur + 1)){
int bit = arrInput.length - i - 1;
int left = 'Z' - cur;
num += comNum(left, bit);
}
}
}
return num;
}
public static int comNum(int num, int top){
if(top == 0)
return 0;
int value = 0;
int tmp1 = 1, tmp2 = 1;
for(int i = 0 ; i < top; i++){
tmp1 *= (num-i);
tmp2 *= (top-i);
}
value = tmp1/tmp2;
return value;
}
public static void main(String[] args){
System.out.println(GetSequenceNum(5, "vwxyz"));
}
}
public class SeqTONum {
private final static int ALPHABETNUM = 26;
public static int GetSequenceNum(int numberOfChars, String input)
{
char[] arrInput = input.toUpperCase().toCharArray();
/*
* Test some illegal situations
* Return 0 if illegal
*/
if (numberOfChars <=0 || numberOfChars > 26)
return 0;
if (arrInput.length > numberOfChars)
{
return 0;
}
if (arrInput.length > 1){
for (int i = 0; i < arrInput.length-2; i++){
if(arrInput[i]>=arrInput[i+1])
return 0;
}
}
/*
* Seq to Num
*/
int num = 0;
if( arrInput.length == 1){
num +=(int)arrInput[0] - ((int) 'A') + 1;
return num;
}
for(int i = 0; i < arrInput.length -1 ; i++){
num += comNum(ALPHABETNUM, i + 1);
}
for(int i = 0; i < arrInput.length; i++) {
if(i==0){
for(char first = 'A'; first < arrInput[0]; first = (char)(first + 1)){
int bit = arrInput.length - 1;
int left = 'Z' - first;
num += comNum(left, bit);
}
} else if(i == arrInput.length-1){
num += (arrInput[i]-arrInput[i-1]);
} else{
for(char cur = (char)(arrInput[i-1] + 1); cur < arrInput[i]; cur = (char)(cur + 1)){
int bit = arrInput.length - i - 1;
int left = 'Z' - cur;
num += comNum(left, bit);
}
}
}
return num;
}
public static int comNum(int num, int top){
if(top == 0)
return 0;
int value = 0;
int tmp1 = 1, tmp2 = 1;
for(int i = 0 ; i < top; i++){
tmp1 *= (num-i);
tmp2 *= (top-i);
}
value = tmp1/tmp2;
return value;
}
public static void main(String[] args){
System.out.println(GetSequenceNum(5, "vwxyz"));
}
}
not sure this is optimized code.
but written based on getting number and subtracting invalid strings from that.
#include<iostream>
#include<string>
using namespace std;
// to compare strings of different lengths.
int string_compare(string str1,string str2)
{
if(str1.length() > str2.length())
return 1;
return str1.compare(str2);
}
// to get number corresponding to the string.
int get_number(string str)
{
int result = 0;
for(int i=0; i<str.length(); i++)
result = result*26 + (str[i]-96);
return result;
}
// to check whether strings are in increasing order or not?
// returns true for abc
// returns false for aab
bool is_valid(string str)
{
bool result = true;
for(int i=0; i<str.length()-1; i++)
{
if(str[i]>=str[i+1])
{
result = false;
break;
}
}
return result;
}
void print_permute(string str,int length,int& count,string stopper,string local="")
{
if(string_compare(stopper,local)>=0)
{
if(length == 0)
{
if(!is_valid(local))
{
// uncommnet below line to find invalid strings.
// cout << " Got Invalid String " << local << endl;
count++;
}
}
else
{
for(int i=0; i<str.length(); i++)
{
print_permute(str,length-1,count,stopper,local+str[i]);
}
}
}
}
int main()
{
int invalid_count = 0;
string str = "abcdefghijklmnopqrstuvwxyz";
string local_string;
cout << " Enter name of string to find its sequence number ";
cin >> local_string;
cout << endl;
if(is_valid(local_string))
{
for(int i=2; i<=local_string.length(); i++)
{
print_permute(str,i,invalid_count,local_string);
}
cout << " Sequence number of string " << local_string << " is " << (get_number(local_string)-invalid_count) << endl;
}
else
cout << " Sequence number of string " << local_string << " is " << invalid_count << endl;
return 0;
}
#include<iostream>
#include<conio.h>
#include<cstring>
#include<cmath>
using namespace std;
int cal1(char a[]);
int cal2(char a[]);
int cal3(char a[]);
int cal(char a);
int miss2();
int miss3();
int main()
{
char *c;
int size,ch;
do
{
cout<<"Input size ";
cin>>size;
c = new char[size];
cout<<"INPUT: ";
cin>>c;
for(int i=0; i<size-1; i++)
{
if(c[i]>c[i+1])
{
cout<<"INVALID INPUT\n";
break;
}
}
int val=0;
if(size==1)
val = cal1(c);
else if(size==2)
val = cal2(c);
else if(size==3)
val = cal3(c);
cout<<val;
cout<<"press 1 to add more";
cin>>ch;
}
while(ch==1);
getch();
return 0;
}
int cal1(char a[])
{
return int(a[0])-96;
}
int cal2(char a[])
{
int x=0;
for(int i=0; i<strlen(a); i++)
x+= pow(26,strlen(a)-1-i) * cal(a[i]);
int p = int(a[0])-96;
return x - (p*(p+1))/2;
}
int cal3(char a[])
{
int x=0;
for(int i=0; i<strlen(a); i++)
x+= pow(26,strlen(a)-1-i)*cal(a[i]);
int p = cal(a[0])-1;
int q=0;
for(int j=0; j<p; j++)
{
for(int k=2+j; k<=26; k++)
q+= k;
}
p = 26*((p*(p+1))/2);
p+= q;
p+= cal(a[1]);
q = cal(a[0]);
q*= 26;
for(int i=0; i<cal(a[1])-cal(a[0])-1; i++)
q+= cal(a[0])+i+1;
x-= miss2() + p + q;
return x;
}
int cal(char a)
{
return int(a)-96;
}
int miss2()
{
return (26*27)/2;
}
#include<iostream>
#include<conio.h>
#include<cstring>
#include<cmath>
using namespace std;
int cal1(char a[]);
int cal2(char a[]);
int cal3(char a[]);
int cal(char a);
int miss2();
int miss3();
int main()
{
char *c;
int size,ch;
do
{
cout<<"Input size ";
cin>>size;
c = new char[size];
cout<<"INPUT: ";
cin>>c;
for(int i=0; i<size-1; i++)
{
if(c[i]>c[i+1])
{
cout<<"INVALID INPUT\n";
break;
}
}
int val=0;
if(size==1)
val = cal1(c);
else if(size==2)
val = cal2(c);
else if(size==3)
val = cal3(c);
cout<<val;
cout<<"press 1 to add more";
cin>>ch;
}
while(ch==1);
getch();
return 0;
}
int cal1(char a[])
{
return int(a[0])-96;
}
int cal2(char a[])
{
int x=0;
for(int i=0; i<strlen(a); i++)
x+= pow(26,strlen(a)-1-i) * cal(a[i]);
int p = int(a[0])-96;
return x - (p*(p+1))/2;
}
int cal3(char a[])
{
int x=0;
for(int i=0; i<strlen(a); i++)
x+= pow(26,strlen(a)-1-i)*cal(a[i]);
int p = cal(a[0])-1;
int q=0;
for(int j=0; j<p; j++)
{
for(int k=2+j; k<=26; k++)
q+= k;
}
p = 26*((p*(p+1))/2);
p+= q;
p+= cal(a[1]);
q = cal(a[0]);
q*= 26;
for(int i=0; i<cal(a[1])-cal(a[0])-1; i++)
q+= cal(a[0])+i+1;
x-= miss2() + p + q;
return x;
}
int cal(char a)
{
return int(a)-96;
}
int miss2()
{
return (26*27)/2;
}
#include<iostream>
#include<cstring>
using namespace std;
char st[100];
int func(char *st);
int main()
{
int i,in,j;
cout<<"\nenter string\n";
cin>>st;
cout<<"\n"<<func(st);
}
int func(char *st)
{
if(!strcmp(st,"z"))
return 26;
int l=strlen(st);
int len=l,in,i;
for(i=0;i<l-1;i++)
if(st[i]>st[i+1])
return 0;
l--;
char t,t1,*st1;
t=st[l];
while(true){
if(l>0 && t-1!=st[l-1]){
st[l]=--t;
in=len-1;
t1='z';
while(in>l){
st[in]=t1;
t1--;
in--;
}
//cout<<"\nc1"<<st<<"\n";
break;
}
else
if( l>0&& t-1==st[l-1])
{
l--;
t=st[l];
//cout<<"\nc2"<<st<<"\n";
}
if(l==0&& st[l]=='a')
{
in=len-2;
t1='z';
while(in>=0){
st[in]=t1;
t1--;
in--;
}
st[len-1]='\0';
//cout<<st;
//cout<<"\nc3"<<st;
break;
}
if(l==0 && st[l]!='a')
{
--st[l];
in=len-1;
t1='z';
while(in>l){
st[in]=t1;
t1--;
in--;
}
//cout<<"\nc4"<<st;
break;
}
}
//cout<<"\n"<<st;
return 1+func(st);
}
#include<iostream>
#include<cstring>
using namespace std;
char st[100];
int func(char *st);
int main()
{
int i,in,j;
cout<<"\nenter string\n";
cin>>st;
cout<<"\n"<<func(st);
}
int func(char *st)
{
if(!strcmp(st,"z"))
return 26;
int l=strlen(st);
int len=l,in,i;
for(i=0;i<l-1;i++)
if(st[i]>st[i+1])
return 0;
l--;
char t,t1,*st1;
t=st[l];
while(true){
if(l>0 && t-1!=st[l-1]){
st[l]=--t;
in=len-1;
t1='z';
while(in>l){
st[in]=t1;
t1--;
in--;
}
//cout<<"\nc1"<<st<<"\n";
break;
}
else
if( l>0&& t-1==st[l-1])
{
l--;
t=st[l];
//cout<<"\nc2"<<st<<"\n";
}
if(l==0&& st[l]=='a')
{
in=len-2;
t1='z';
while(in>=0){
st[in]=t1;
t1--;
in--;
}
st[len-1]='\0';
//cout<<st;
//cout<<"\nc3"<<st;
break;
}
if(l==0 && st[l]!='a')
{
--st[l];
in=len-1;
t1='z';
while(in>l){
st[in]=t1;
t1--;
in--;
}
//cout<<"\nc4"<<st;
break;
}
}
//cout<<"\n"<<st;
return 1+func(st);
}
Here is the logic,
You can think the number of possibilities id dependent on the previous number.
NumCount = (Sum of 1 from 1 to 26) + (Sum of (Sum of 1 from j+1 to 26) from 1 to 26 as j + (Sum of (Sum of (Sum of 1 from j+1 to 26) from i+1 to 26 as j) from 1 to 26 as i + ...
it is like first digit have 26 possibilities, second can only take 26-first digit position (example : if first digit is 'e', second can take any value from f to z), similarly third, fourth ...so on
this will go upto inputStr.Length-1, but the last string possibilities are based upon the digit.
(for example input is 'eftr' now to calculate four digit possible count, first digit can change from a to e, second can change from first to f, third from second to t, and fourth from third to r).
Now all we have to do it calculate this sum.
public class _26BaseToDecimal
{
char[] alpha = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
public void lettersToDecimal(string input, int baseN=26)
{
int decimalN = 0;
for (int i = 0; i < input.Length; i++)
{
// aasci value for 'a' is 97 so, a-a + 1=97-97 + 1= 1 , So a=>1, b-a+1=98-97+1=2, so b=>2 (mapping)
decimalN = decimalN * baseN + int.Parse((input[i] - 'a' + 1).ToString());
}
Console.WriteLine("For alphabate {0} decimal is {1}", input, decimalN);
}
}
public int GetSequenceNo(int numberOfChars, string input)
{
var arrInput = input.ToUpper().ToCharArray();
bool isValid = true;
if (numberOfChars <=0 || numberOfChars > 26)
return 0;
//Only allow alphabets, therefore max length of valid input is 26
if (arrInput.Length > numberOfChars)
{
return 0;
}
if (arrInput.Length == 1)
return (int)arrInput[0] - ((int) 'A');
for(int i=0;i<arrInput.length-2;i++)
{
if((int)arrInput[i]>(int)arrInput[i+1])
{
isValid=false;
break;
}
}
if (!isValid)
return 0;
int[] arrValue = new int[arrInput.Length+1];
for (int i=0; i < arrInput.Length; i++)
{
arrValue[i] = (int)arrInput[i] - ((int) 'A');
}
arrValue[0] = 0;
long seq = 0;
int size = arrInput.Length;
bool substracted = false;
int i = 0;
while (arrValue[size-1] > 0)
{
seq += (int)arrValue[size-1] - (int)arrValue[size-2];
if (arrValue[size-2] > 0)
{
arrValue[size-1] = numberOfChars;
substracted = false;
i = size - 2;
do
{
arrValue[i] -= 1;
if(arrValue[i-1] > 0)
{
if (arrValue[i-1] == arrValue[i])
{
arrValue[i] = numberOfChars - 3 + i + 1;
i-=1
}
else
{
substracted = true;
}
}
else
{
substracted = true;
}
} while (!substracted)
}
else
{
arrValue[size-1] = 0;
}
}
return seq;
}
Minor fix:
for (int i=0; i < arrInput.Length; i++)
{
arrValue[i] = (int)arrInput[i] - ((int) 'A');
}
arrValue[0] = 0;
should change to:
for (int i=0; i < arrInput.Length; i++)
{
arrValue[i+1] = (int)arrInput[i] - ((int) 'A');
}
arrValue[0] = 0;
public int GetSequenceNo(int numberOfChars, string input)
{
var arrInput = input.ToUpper().ToCharArray();
bool isValid = true;
if (numberOfChars <=0 || numberOfChars > 26)
return 0;
//Only allow alphabets, therefore max length of valid input is 26
if (arrInput.Length > numberOfChars)
{
return 0;
}
if (arrInput.Length == 1)
return (int)arrInput[0] - ((int) 'A');
for(int i=0;i<arrInput.length-2;i++)
{
if((int)arrInput[i]>(int)arrInput[i+1])
{
isValid=false;
break;
}
}
if (!isValid)
return 0;
int[] arrValue = new int[arrInput.Length+1];
for (int i=0; i < arrInput.Length; i++)
{
arrValue[i+1] = (int)arrInput[i] - ((int) 'A');
}
arrValue[0] = 0;
long seq = 0;
int size = arrInput.Length;
bool substracted = false;
int i = 0;
while (arrValue[size] > 0)
{
seq += (int)arrValue[size] - (int)arrValue[size-1];
if (arrValue[size-1] > 0)
{
arrValue[size] = numberOfChars;
substracted = false;
i = size - 1;
do
{
arrValue[i] -= 1;
if(arrValue[i-1] > 0)
{
if (arrValue[i-1] == arrValue[i])
{
arrValue[i] = numberOfChars - size + i + 1;
i-=1
}
else
{
substracted = true;
}
}
else
{
substracted = true;
}
} while (!substracted)
}
else
{
arrValue[size] = 0;
}
}
return seq;
}
When I tested this function with this input:
Console.WriteLine(GetSequenceNo(3, "aez"));
It returned 27 which is not correct, aez should return 441.
numberOfChars: number of valid characters, e.g. 3 means only a, b, c are valid characters.
Thanks for your test case. I think I need to add validation logic for this right after 2nd if statement:
for(int i=0;i<arrInput.length-1;i++)
{
if((int)arrInput[i] >= ((int) 'A') + numberOfChars || (int) arrInput[i] < ((int)'A'))
{
isValid=false;
break;
}
}
if (!isValid) return 0;
ideone.com/tJRIsZ
- Anonymous July 05, 2013