Test job - Split Array

readme.md

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.

ArraySplitter.php

<?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();

If the question says Assume that: why do we need to validate that they are supplying that data?

What was your correctness? Also, it doesn't meet the complexity requirement.

I've recently faced the same task. If you don't mind here's the solution that I believe meets all the requirements: https://github.com/Jarosh/Exercises/wiki/Split-array-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