aboutsummaryrefslogtreecommitdiff
path: root/magical_string.c
diff options
context:
space:
mode:
Diffstat (limited to 'magical_string.c')
-rw-r--r--magical_string.c38
1 files changed, 38 insertions, 0 deletions
diff --git a/magical_string.c b/magical_string.c
new file mode 100644
index 0000000..d04a5d1
--- /dev/null
+++ b/magical_string.c
@@ -0,0 +1,38 @@
+// 481. Magical String
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * a magical string 's' consists of only '1' & '2' and obeys the following rules
+ * the string 's' is magical because concatenating the number of contiguous
+ * occurences of characters '1' & '2' generates the string 's' itself. given
+ * integer 'n', return the number of 1's in the first 'n' number in the magical
+ * string 's'.
+ */
+
+int magicalString(int n) {
+ char *s = malloc(sizeof(char) * (n + 1));
+ s[0] = '1';
+ s[1] = '2';
+ s[2] = '2';
+ int i = 2, cnt = 0, k = i;
+ while (k < n - 1) {
+ int c_i = s[i] - '0';
+ char ch = s[k];
+ for (int j = 0; j < c_i; j++) {
+ s[k + 1] = ch ^ 3;
+ k++;
+ }
+ i++;
+ }
+ s[k + 1] = '\0';
+ for (i = 0; i < n; i++)
+ if (s[i] == '1')
+ cnt++;
+ return cnt;
+}
+
+int main() {
+ printf("%d\n", magicalString(6)); // expect: 3
+ printf("%d\n", magicalString(1)); // expect: 1
+}