fimak · July 30, 2016 21:51 · Feb 9, 2015 · Feb 9, 2015 · Feb 9, 2015 · Feb 6, 2015
diff --git a/ArraySplitter.py b/ArraySplitter.py
@@ -0,0 +1,72 @@
+class ArraySplitter:
+    def __init__(self, x, a):
+        self.validation(x, a)
+        self.x = x
+        self.a = a
+        self.left = 0
+        self.right = 0
+        self.n = len(a)
+        if self.n > 2:
+            self.k = round(self.n/2)
+        else:
+            self.k = 0
+
+    def validation(self, x, a):
+        if not(0 < x < 100000) or not int(x):
+            raise ValueError('Oops! That was not valid number.')
+        if len(a) < 1:
+            raise ValueError('Oops! That was not valid array')
+        if not a.count(x):
+            raise ValueError('Oops! No one element from array is equal to X.')
+        for item in a:
+            if not(0 < item < 100000) or not int(item):
+                raise ValueError('Oops! That was not valid array')
+
+    def to_split(self, is_equal = False):
+        for i in range(self.n):
+            is_equal = self.check_parts(self.k)
+            if is_equal:
+                print("Splitted at index = " + str(self.k))
+                return self.k
+            if self.left > self.right:
+                self.k -= self.left - self.right
+            elif self.left < self.right:
+                self.k += self.right - self.left
+        print("Can't to split the array")
+        return False
+
+    def check_parts(self, index):
+        left = 0
+        for i in range(index):
+            if self.a[i] == self.x:
+                left += 1
+        right = 0
+        for i in range(index + 1, len(self.a)):
+            if self.a[i] != self.x:
+                right += 1
+        if left == right:
+            return True
+        else:
+            self.left = left
+            self.right = right
+            return False
+
+x = 5
+a = [5, 5, 1, 7, 2, 3, 5]
+
+model = ArraySplitter(x, a)
+
+print(model.x, model.a)
+print(model.n, model.k)
+
+model.to_split()
+
+left = {}
+right = {}
+for (key, value) in enumerate(model.a):
+    if key in range(0, model.k + 1):
+        left[key] = value
+    else:
+        right[key] = value
+print(left)
+print(right)
diff --git a/readme.md b/readme.md
@@ -1,3 +1,6 @@
+The task from interview.
+There are two versions of this script written in php and python.
+
 An integer X and a non-empty zero-indexed array A consisting of N integers are given. We are interested in which elements of A are equal to X and which are different from X. The goal is to split array A into two parts, such that the number of elements equal to X in the first part is the same as the number of elements different from X in the other part. More formally, we are looking for an index K such that: 0 ≤ K < N and the number of elements equal to X in A[0..K−1] is the same as the number of elements different from X in A[K..N−1]. For K = 0, A[0..K−1] does not contain any elements.
 
 For example, given integer X = 5 and array A such that:

diff --git a/ArraySplitter.php b/ArraySplitter.php
@@ -20,7 +20,7 @@ public function __construct($x, $a)
         $this->x = $x;
         $this->a = $a;
         $this->n = count($a);
-        if ($this->n >= 2) {
+        if ($this->n > 2) {
             $this->k = round($this->n/2); //start to find from middle
         } else {
             $this->k = 0; //start to find from begining

diff --git a/ArraySplitter.php b/ArraySplitter.php
@@ -20,7 +20,7 @@ public function __construct($x, $a)
         $this->x = $x;
         $this->a = $a;
         $this->n = count($a);
-        if ($this->n <= 2) {
+        if ($this->n >= 2) {
             $this->k = round($this->n/2); //start to find from middle
         } else {
             $this->k = 0; //start to find from begining

diff --git a/ArraySplitter.php b/ArraySplitter.php
@@ -0,0 +1,104 @@
+<?php
+
+class ArraySplitter
+{
+    public $x; //the X
+    public $a; //array
+    public $n; //count of all elements
+    public $k; //index of searching
+    public $left; //count of $x in left part
+    public $right; //count of !$x in right part
+
+    public function __construct($x, $a)
+    {
+        try {
+            $this->validation($x, $a);
+        } catch (Exception $e) {
+            echo "Exception: " . $e->getMessage() . "\n";
+            die();
+        }
+        $this->x = $x;
+        $this->a = $a;
+        $this->n = count($a);
+        if ($this->n <= 2) {
+            $this->k = round($this->n/2); //start to find from middle
+        } else {
+            $this->k = 0; //start to find from begining
+        }
+    }
+
+    public function validation($x, $a)
+    {
+        if ($x < 0 || $x > 100000 || !is_int($x)) {
+            throw new Exception("The X must be integer, 0 < X < 100000\n");
+        }
+        if (count($a) < 1) {
+            throw new Exception("The count of array must be > 1", 1);
+        }
+        foreach ($a as $value) {
+            if ($value < 0 || $value > 100000 || !is_int($value)) {
+                throw new Exception("Each element of array must be integer and > 0 and <100000\n");
+            }
+        }
+        if (!in_array($x, $a)) {
+            throw new Exception("No one element from array is equal to X\n");
+        }
+    }
+
+    public function toSplit($isEqual = false)
+    {
+        for ($i = 0; $i < $this->n; $i++) {
+            $isEqual = $this->checkParts($this->k);
+            if ($isEqual) {
+                echo "Splitted at index = $this->k \n";
+                var_dump(array_slice($this->a, 0, $this->k+1, true));
+                var_dump(array_slice($this->a, $this->k+1, $this->n));
+                return $this->k;
+            }
+            if ($this->left > $this->right) {
+                $this->k -= ($this->left - $this->right);
+            } elseif ($this->left < $this->right) {
+                $this->k += ($this->right - $this->left);
+            }
+        }
+        echo "Can't to split the array \n";
+        return false;
+    }
+
+    public function checkParts($index)
+    {
+        //check left part of $a
+        $left = 0;
+        for ($i = 0; $i < $index; $i++) {
+            if ($this->a[$i] === $this->x) {
+                $left++;
+            }
+        }
+        //check right part of $a
+        $right = 0;
+        for ($i = $index+1; $i < count($this->a); $i++) {
+            if ($this->a[$i] != $this->x) {
+                $right++;
+            }
+        }
+        //check parts
+        if ($left === $right) {
+            return true;
+        } else {
+            $this->left = $left;
+            $this->right = $right;
+            return false;
+        }
+    }
+}
+
+$x = 5;
+$a = [5, 5, 1, 7, 2, 3, 5];
+
+$model = new ArraySplitter($x, $a);
+
+echo "X = $model->x \n";
+echo "N = $model->n \n";
+var_dump($model->a);
+
+$model->toSplit();
diff --git a/readme.md b/readme.md
@@ -0,0 +1,23 @@
+An integer X and a non-empty zero-indexed array A consisting of N integers are given. We are interested in which elements of A are equal to X and which are different from X. The goal is to split array A into two parts, such that the number of elements equal to X in the first part is the same as the number of elements different from X in the other part. More formally, we are looking for an index K such that: 0 ≤ K < N and the number of elements equal to X in A[0..K−1] is the same as the number of elements different from X in A[K..N−1]. For K = 0, A[0..K−1] does not contain any elements.
+
+For example, given integer X = 5 and array A such that:
+
+A = [5, 5, 1, 7, 2, 3, 5]
+
+K equals 4, because:
+two of the elements of A[0..3] are equal to X, namely A[0] = A[1] = X, and
+two of the elements of A[4..6] are different from X, namely A[4] and A[5].
+
+Write a function solution($X, $A); that, given an integer X and a non-empty zero-indexed array A consisting of N integers, returns the value of index K satisfying the above conditions. If more than one index K satisfies the above conditions, your function may return any of them. If there is no such index, the function should return −1.
+
+For example, given integer X and array A as above, the function should return 4, as explained above.
+
+Assume that:
+N is an integer within the range [1..100,000];
+X is an integer within the range [0..100,000];
+Each element of array A is an integer within the range [0..100,000].
+
+Complexity:
+Expected worst-case time complexity is O(N);
+Expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments);
+Elements of input arrays can be modified.