diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/arithmetic_progression.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/arithmetic_progression.cpp')
-rw-r--r-- | other/arithmetic_progression.cpp | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/other/arithmetic_progression.cpp b/other/arithmetic_progression.cpp new file mode 100644 index 0000000..4c1c996 --- /dev/null +++ b/other/arithmetic_progression.cpp @@ -0,0 +1,44 @@ +// 1502. Can Make Arithmetic Progression From Sequence +#include "leetcode.h" + +/* + * a sequence of numbers is called an arithmetic progression if the difference + * between any two consecutive elements is the same. gien an array of numbers + * 'arr', return true if the array can rearranged to form an arithmetic + * progression. otherwise, return false. + */ + +class Solution { +public: + bool canMakeArithmeticProgression(vector<int> &arr) { + if (arr.size() <= 2) + return true; + auto min = *min_element(begin(arr), end(arr)); + auto max = *max_element(begin(arr), end(arr)); + if ((max - min) % (arr.size() - 1)) + return false; + int d = (max - min) / (arr.size() - 1); + for (int i = 0; i < arr.size();) { + if (arr[i] == min + i * d) + i++; + else if ((arr[i] - min) % d) + return false; + else { + int pos = (arr[i] - min) / d; + if (pos < i) + return false; + if (arr[pos] == arr[i]) + return false; + swap(arr[i], arr[pos]); + } + } + return true; + } +}; + +int main() { + Solution obj; + vector<int> a1 = {3, 5, 1}, a2 = {1, 2, 4}; + printf("%d\n", obj.canMakeArithmeticProgression(a1)); // expect: 1 + printf("%d\n", obj.canMakeArithmeticProgression(a2)); // expect: 0 +} |