Java array handling. Algorithm solving.

unicio

Hi All,

I was solving algorithm question from Hackerrank. I came across that you can't make a huge array in Java due to the limitation of memories.


►You will be given String s and int n.

String s = "aba" : or "a" or "abcab" .. anything.
int n = "10" : 1 <n <10¹²

Condition 1.
- The string 's' will be infinitely repeated until when it's length to reach to 'n'

Condition 2.
- Count how many letter 'a' come up in the string within 'n' length.

Example.

s : aba
n :10

abaabaabaa --> answer 7.

s: a
n: 10000000000000

aaa................aa --> answer 10000000000000.

Then how would you approach this problem?
I succeed in the first example, but won't be able to make the second example due to a limitation of the size of an array.
I can't think of the other way around not using arrays.

Following is my approach.

[HTML]

static long repeatedString(String s, long n) {

char[] array = s.toCharArray();
char[] resultArray = new char[(int) n];

int result = 0;

if(array.length < n){
int count = 0;
for(int i=0; i<resultArray.length; i++){
if(i < array.length ){
resultArray = array;
} else {
resultArray = array[i % array.length];
}
if(resultArray == 'a') count++;
}
result = count;
} else {
int count = 0;
for (int i=0; i<array.length; i++){
if(array == 'a') count++;
}
result = count;
}

return result;
}

[/HTML]

https://www.hackerrank.com/challenges/repeated-string/problem

Pelvis

In your second example your string has only a length of one, so your answer will be n.

unicio

Pelvis wrote: »

In your second example your string has only a length of one, so your answer will be n.

Yeah, I know it. but how would you implement a method?

Pelvis

At the start of your method, do a check to see if your string equals 'a'. If true, return n.

unicio

Pelvis wrote: »

At the start of your method, do a check to see if your string has a length of 1 and equals 'a'. If true, return n.

What if given example was,

s = "abc"
n = 10000000000000

How would you solve this? Checking the length of 'any number' at the start is not the best approach I say.
And Point I was making is that My problem is I can't make a huge array. (ex, char[] c = new char[100000000000] --> I can't do this)

Apiarist

I would not create the very long string (resultArray) in the first instance.

The algorithm:
1) Calculate how many whole strings "s" fit into n, say this is M. Count how many "a"'s are in "s", this is F.
2) Determine if there is a part of "s" which did not fit fully into n-character string. (NB: use remained operator %: n % s.length() = X). Count occurances of a in the first X characters of "S", say this is C.
3) Your answer is C + M*F

Tom1991

Pelvis wrote: »

At the start of your method, do a check to see if your string equals 'a'. If true, return n.

This holds for the pattern as well if you enter “aba” that’s repeated x times all you have to do is count how many times a appears in that pattern and multiply it by n.
Thus it holds for any pattern that’s given that you know will be repeated.

It’s more to see if you can divide the problem into its simplest case and see through the wool placed around it.u could put your foot in it on a whiteboard(as I have done and panicked) and gone looping through the array and counting the a’s.

unicio

victor8600 wrote: »

I would not create the very long string (resultArray) in the first instance.

The algorithm:
1) Calculate how many whole strings "s" fit into n, say this is M. Count how many "a"'s are in "s", this is F.
2) Determine if there is a part of "s" which did not fit fully into n-character string. (NB: use remained operator %: n % s.length() = X). Count occurances of a in the first X characters of "S", say this is C.
3) Your answer is C + M*F

Thanks Victor8600,

I managed to do it.

[HTML]
static long repeatedString(String s, long n) {

char[] array = s.toCharArray();
long count = 0;
long countRemain = 0;
long times = (n / array.length);
long reminder = (n % array.length);

for(int i=0; i<array.length; i++){
if(array =='a'){
count++;
}
}

for(int i=0; i<reminder; i++){
if(array =='a'){
countRemain++;
}
}

long result = count * times + countRemain;
return result;
}
[/HTML]