Skip to content

Instantly share code, notes, and snippets.

@JulienRouse
Created May 23, 2017 11:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JulienRouse/ff346ea8068a622017b3b4cd60408f53 to your computer and use it in GitHub Desktop.
Save JulienRouse/ff346ea8068a622017b3b4cd60408f53 to your computer and use it in GitHub Desktop.
Algo naive for GeometricTrick challenge
/**
* Consider a string s of length n with alphabet {a,b,c}.
* We look for the number of different triplet (i,j,k) where 0<=i,j,k<n, satisfying!
* - s[i] = "a", s[j] = "b", s[k] = "c"
* - (j + 1)² = (i + 1)(k + 1)
* @param s A string we look the triplet in
* @return Number of different triplets such as enonced above.
*/
public static int geometricTrick(String s){
//extract index for a,b and c in lists
List<Integer> indexA = new ArrayList<>(s.length());
List<Integer> indexB = new ArrayList<>(s.length());
List<Integer> indexC = new ArrayList<>(s.length());
//here we fill the lists created just above
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='a')
indexA.add(i);
if(s.charAt(i)=='b')
indexB.add(i);
if(s.charAt(i)=='c')
indexC.add(i);
}
//and then we try to find indexes satisfying the condition
int res = 0;
for(int tmpA:indexA)
for(int tmpB:indexB)
for(int tmpC:indexC)
if(((tmpB+1)*(tmpB+1))==((tmpA+1)*(tmpC+1)))
res++;
return res;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment