Created
May 23, 2017 11:58
-
-
Save JulienRouse/ff346ea8068a622017b3b4cd60408f53 to your computer and use it in GitHub Desktop.
Algo naive for GeometricTrick challenge
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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