diff options
| author | 冯昶 <fengchang@novel-supertv.com> | 2023-07-10 17:40:21 +0800 |
|---|---|---|
| committer | 冯昶 <fengchang@novel-supertv.com> | 2023-07-10 17:40:21 +0800 |
| commit | 75e4052bf46c76dc87c719ded35e62beb1031c4c (patch) | |
| tree | 3e0771213cc7111f5a2558949b83cda3240c9c0c /challenge-224/eric-cheung/python/ch-2.py | |
| parent | 80a35465e9e45a3bebbd5e82969a16d61bb9a858 (diff) | |
| parent | 80e57ec8f3de321e2f66184490f16b335a281896 (diff) | |
| download | perlweeklychallenge-club-75e4052bf46c76dc87c719ded35e62beb1031c4c.tar.gz perlweeklychallenge-club-75e4052bf46c76dc87c719ded35e62beb1031c4c.tar.bz2 perlweeklychallenge-club-75e4052bf46c76dc87c719ded35e62beb1031c4c.zip | |
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'challenge-224/eric-cheung/python/ch-2.py')
| -rwxr-xr-x | challenge-224/eric-cheung/python/ch-2.py | 87 |
1 files changed, 87 insertions, 0 deletions
diff --git a/challenge-224/eric-cheung/python/ch-2.py b/challenge-224/eric-cheung/python/ch-2.py new file mode 100755 index 0000000000..8f0bbc99ee --- /dev/null +++ b/challenge-224/eric-cheung/python/ch-2.py @@ -0,0 +1,87 @@ +
+## Remarks
+## https://www.geeksforgeeks.org/string-with-additive-sequence-set-2/
+
+## python3 code to implement the approach
+
+## Variable to store the result
+bResult = False
+arrStr = []
+
+## Function to check the additive sequence
+def check_additive(strIn, subStrIn):
+ global bResult
+ global arrStr
+
+ ## If the end is reached and vector consists of more than 2 numbers, then one of the possible solution is found
+ if (subStrIn == len(strIn) and len(arrStr) > 2):
+
+ ## Mark the bResult as true to indicate the solution is found and to avoid for trying the rest of the combinations
+ bResult = True
+ return
+
+ nInt_01, nInt_02, nInt_03 = 0, 0, 0
+
+ if (len(arrStr) >= 2):
+ ## Store the previous two numbers of the sequence to check the additive sequence property for the next number
+ nInt_02 = arrStr[len(arrStr) - 1]
+ nInt_01 = arrStr[len(arrStr) - 2]
+
+ for nIndxLoop in range(subStrIn, len(strIn)):
+
+ ## Generate the number
+ nInt_03 = nInt_03 * 10 + ord(strIn[nIndxLoop]) - ord("0")
+
+ ## Try all the possible ways to generate the first two numbers
+ ## i.e. if vector consists of less than two numbers and no solution is found yet
+ if (len(arrStr) < 2):
+ arrStr.append(nInt_03)
+ check_additive(strIn, nIndxLoop + 1)
+
+ ## Pop the value to try for the other combination
+ arrStr.pop()
+
+ ## If the number generated so far is not equal the sum of previous two numbers in the sequence
+ ## then it cannot be a part of additive sequence hence no need to proceed further
+
+ return
+
+ if (nInt_03 != nInt_01 + nInt_02):
+ return
+
+ ## If the number generated so far is equal to the sum of previous two numbers
+ ## then it can be a part of additive sequence
+ ## push it into vector and check for remaining string
+
+ ## Store it in the vector
+ arrStr.append(nInt_03)
+
+ ## Recur for remaining string
+ check_additive(strIn, nIndxLoop + 1)
+
+ ## If unable to find solution
+ ## pop it and try for other combination
+ arrStr.pop()
+
+ return
+
+## Function to check if additive sequence
+def IsAdditiveSeq(strInputFunc):
+ global bResult
+
+ ## In order to form additive sequence, the length of the string must be at least three
+ if (len(strInputFunc) <= 2):
+ return False
+
+ bResult = False
+ check_additive(strInputFunc, 0)
+ return bResult
+
+## Driver Code
+if __name__ == "__main__":
+
+ ## strInput = "112358" ## Example 1
+ ## strInput = "12345" ## Example 2
+ strInput = "199100199" ## Example 3
+
+ print (IsAdditiveSeq(strInput))
|