CareerCup

It's actually not that trivial. Did you overlook some details? If you can't use extra space and "aaa" takes up more space than "a3", you will overwrite the "b" in "b4". The trick is to determine how much space is needed first, treat that as the back of the array, and start placing letters there (work from the back). But even with that approach, you have to be careful because if you have text like "a3b2c2a1a1a1", you're going to overwrite the middle of the string with this algorithm because "a1" is longer than "a". You might have to do a pass to eliminate instances of things like "a1" and "a0" and get the string to a form where every encrypted form is shorter than or equal length to the decrypted form.

Maybe there's a better way to do it, but it doesn't seem that simple. But a question to you: would your algorithm have passed the case "a3b2c2a1a1a1"?

Pseudo code

start =0;
end = length of crypt array - 1;

while(start<end)
{
if(arr[end - 2] < end - 1) // condition to check whether we can decrypt from backwards
{
copy the elements from back of an array ;
end = end+2;
}
else  // deecrypt from front of an array
{
copy the elements from front of an array;
start = start +2;
}

}

correct me if i am wrong .. thank you

<pre lang="" line="1" title="CodeMonkey32792" class="run-this">
#include<iostream>
#include<math.h>

using namespace std;

int main()
{
char op[4];
int n=3;
int i,j,a,m;

for( i=0 ; i<pow(2,n) ;i++)
{
m=i;

for(j=0;j<n;j++)
{

a = 1;
a = m & 1;
m=(m>>1);

if(a==0)
{
op[j]='p';
}
else
{
op[j]='o';
}
}

op[j]='\0';
for(j=0;op[j];j++)
{
cout<<op[j];
}
cout<<"\n";
}
getchar();
return 0;
}
</pre><pre title="CodeMonkey32792" input="yes">
</pre>

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

int main()
{
	char str[100] ;
	int l ; 
	int i , j ,k;
	int ct ; 
	int final ; 
	int use ;
	char ch ; 
	scanf("%s",str);

	l = strlen(str);

	ct = 0 ; 
	for(i = 1 ; i < l ; i+=2)
	{
		ct += (str[i] - '0');
	}

	final = max(l,ct);

	i = final - 1; 
	j = l - 1; 

	while(j >=1)
	{
		use = str[j] - '0';
		ch = str[j-1]; 
		for(k = 0 ; k < use ; k++)
		{
			str[i] = ch; 
			i--;
		}
		j -= 2 ; 
	}

	if(ct >= l)
	{
		str[ct] = '\0';
		printf("%s\n",str);
	}
	else
	{
		for(i = 0 ; i < ct ; i++)
			str[i] = str[i+l-ct] ; 
		str[ct] = '\0';
		printf("%s\n",str);
	}

	return 0;
}

Nice Problem
1.if we start writing from right we may override some information
example a1b1c3
abccc
2. Similarly if we start writing from left we may override some information
example a3b1
aaab
A better example is the combination of both

if we start writing from right we may loose information

example a1b1c3

abccc

if we start writing from left we may loose information

example a3b1

aaab

better example would be the combination

Ques: a 3 b 1 a 1 c 3
I No. of char can be written: 1 2 3 4 5 6 7 8
II No. of char req to be written :1 3 4 4 5 5 6 8
III = I - II: 0-1-1 0 0 1 2 3
ans: a a a b a c c c
fill right to left until III is negative and fill left to right until III is positive

if we start writing from right we may loose information

example a1b1c3

abccc

if we start writing from left we may loose information

example a3b1

aaab

better example would be the combination

Ques: a 3 b 1 a 1 c 3
I No. of char can be written: 1 2 3 4 5 6 7 8
II No. of char req to be written :1 3 4 4 5 5 6 8
III = I - II: 0-1-1 0 0 1 2 3
ans: a a a b a c c c
fill right to left until III is negative and fill left to right until III is positive

Are the numbers present in the crypt array will definitely be single digit?
If yes,we can relax to some extent.
Btw, we got to move the chunks to the right.
Lets design an algo which have minimum copies involved.

Beginning from the right end of the array have the advantage of avoiding the overwrites.
//Pseudo Code
int arr[MAX];
len = length of the crypted array-1;
j = MAX-1;
while(len>=0)
{
int rep = atoi(len);
char c = *(len-1)
while (rep>0)
{
arr[j] = c;
rep--;
j--;
}
len = len -2;
}

The most difficult case would be : b3a1a1a1a1a1a1a1a1a1a1b3
This string contains both expanding and contracting elements.

So, the solution I guess should be :

Pass 1 : Let li=length of input , lo= length of final output
So find value final as -- final=max(l,ct)
Now, contract the contracting strings i.e make your string as b3aaaaaaaaaab3 - O(n) operation

Pass 2: Now this string can ONLY expand. Scan this string (your scanning method will change a little bit now,as odd indices dont neccesarily contain an integer. Deal with it somehow-not a big problem).
So scan this string and start writing from final backwards. - O(n)

Pass 3 : If some space is remaining in the front like in this cas the converted string would be : --------bbbaaaaaaaaaabbb
Where '--------' is trash containing b3a1a1a1. Shift your answer backwards to 'bbbaaaaaaaabbbb--------'

Do let me know if any one finds an error in this method.

Sample code in C#.

void DecryptArray(char[] ch)
{
int index = 0;
int i = 0;
int k = 0;
char c = ' ';

Reverse(ch, 0, ch.Length - 1);

while (true)
{
if (ch[index] == ' ')
index++;
else
break;
}

for (int j = ch.Length - 1; j > index; j -= 2)
{
i = Convert.ToInt32(ch[j - 1].ToString());
c = ch[j];

while (i >= 1)
{
ch[k] = c;
k++;
i--;
}
}
}

void Reverse(char[] ch,int start,int end)
{
while (start < end)
{
char temp = ch[end];
ch[end] = ch[start];
ch[start] = temp;
start++;
end--;
}
}

Lets the array size be N and string input size be M.

1) Copy ( M...0 ) to ( N .. ( N - M ). The order need to reverse so that there is no overwrite.
2) Now have two loop variables i = 0 , j = N - M.
3) Start a loop from j to N
4) start writing to i ..increment i as necessary.

@wavelet: Could you elaborate your algo?

small modification for the above code ..

before entering the while loop .perform the below operation

if d given input is a1b2c3 , add the prev number to the present number which gives you the poistion of next character to place..
i.e in a1b2c3 edited string ll be a1b3c5 so b can be inserted from 1 'c' can be inserted from position 3.

If it's only ascii , we need only 127 for all ASCII. So the most significant bit can be reused to mark whether it's a count number or not. Also the limit is you can only have counter max 127. For example, you have a.....a (128 a), you need encode into:
"127"a1a (127 should be one byte)

It is a trivial Qustion

It is a trivial Question