Solution with breakdowns for some problems of CodersBit conducted by InterviewBit.com at IIIT Bhubaneswar.

CodersBit.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Import Libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "import math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1. Given an array A, find the minimum number of elements that should be filtered from A to give an array B such that every element in B is divisible by every other element."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Breakdown"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "This condition :- `Every element in B is divisible by every other element` is only possible only when all the elements in the array are equal. So, basically, we have to make all the elements in the array equal with removing minimum number of elements. If we keep the element which has maximum frequency and remove remaining elements from the array, that will be our optimal case."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def solve1(a):\n",
    "    freq = collections.Counter(a)\n",
    "    return sum(freq.values()) - max(freq.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Sample Test Case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve1([1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2. Given an array A, find the number of distinct prime factors in the product of all the elements in the array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Breakdown"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "There are 2 ways we can proceed :-\n",
    "1. Get the product first and find its prime factors\n",
    "2. Get the prime factors of individual numbers in the array and take the union of all of them. (The prime factors of the product comes from the prime factors of its constituent factors only).\n",
    "\n",
    "At first sight, 2nd option may seem a bit more time consuming task as we are finding prime factors of a bunch of numbers Vs of a single number, but there is a method(Smallest Prime Factor + Sieve) which has some initial setting up cost, but after that, subsequent queries of finding prime factors is O(log n).\n",
    "This is much more efficient than finding prime factors of the product, as the product may end up being a huge number, and the search space increases exponentially.\n",
    "\n",
    "So, we go with option 2.\n",
    "\n",
    "The idea is to maintain a array just like we do in sieve, but instead of storing just the boolean status of numbers as prime or not, we store the `smallest prime factor` of each number (not necessary to be smallest, largest will also do, or even, as a matter of fact, any prime factor will do. Its just that the largest/smallest P.F. is more convenient to store). We add the recorded prime factor to our answer_set, and then divide the number by this prime factor. Then again, for this new number we got after division, we find its recorded prime factor in the matrx, and the process continues till we end up with the number as 1.\n",
    "\n",
    "The idea basically is to eliminate prime factors from the number one by one. If we store the smallest prime factors, then the order in which we will be eliminating the prime factors would be ascending.\n",
    "If we store largest prime factors, it would be descending. If we store random, it would be random. In the end, the same prime factors only will be eliminated.\n",
    "\n",
    "The table is contructed keeping in mind the maximum number in the array, so that it covers for all other numbers in the array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def solve2(a):\n",
    "    a_max = max(a)\n",
    "    '''\n",
    "    spf of each number is initializaed as the number itself \n",
    "    (which is true for prime numbers only), just similar to initialization for sieve, \n",
    "    in which we initialize all numbers are prime.\n",
    "    ''' \n",
    "    \n",
    "    def generate_spf_matrix(n):    \n",
    "        spf = [i for i in range(n + 1)]\n",
    "\n",
    "        for i in range(4, n + 1, 2):\n",
    "            spf[i] = 2\n",
    "\n",
    "        for i in range(3, math.ceil(math.sqrt(n)), 2):\n",
    "            if spf[i] == i:    # i is prime\n",
    "                for j in range(i*i, n + 1, i):\n",
    "                    if spf[j] == j:\n",
    "                        spf[j] = i\n",
    "        \n",
    "        return spf\n",
    "    \n",
    "    def get_prime_factors(x, spf):\n",
    "        pfs = set()\n",
    "        while x != 1:\n",
    "            pfs.add(spf[x])\n",
    "            x = x // spf[x]\n",
    "        return pfs\n",
    "    \n",
    "    spf = generate_spf_matrix(a_max)\n",
    "    distinct_pfs = set()\n",
    "    for x in a:\n",
    "        distinct_pfs |= get_prime_factors(x, spf)\n",
    "    return len(distinct_pfs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Sample Test Case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve2([10, 50, 35, 39])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q3. Given a number 'n', find the minimum number of primes whose summation gives 'n'. If not possible to represent the number as sum of primes, return -1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Breakdown"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "We start off by creating an integer sieve array, with prime number having value 1 (denoting a single prime needed to get this sum), and all composite number having value `inf`. Let's say the array is named as `dp`.\n",
    "\n",
    "```Python\n",
    "primes = []\n",
    "for i in range(2, n):\n",
    "    if dp[i] == 1:    # i is prime\n",
    "        primes.insert(0, i) # inserting in the beginning so reverse traversing will be convinient\n",
    "    else:             # i is composite, then we try to break it down using all primes smaller than it.\n",
    "        for p in primes:\n",
    "            dp[i] = min(dp[i], dp[i - p] + 1)\n",
    "            if dp[i] == 2: # composite number can't get a lower value than 2\n",
    "                break\n",
    "return (-1 if dp[n] == float(\"inf\") else dp[n])\n",
    "```\n",
    "\n",
    "This solution seems to be decent one. But, still this is costly for large numbers.\n",
    "We can do much better, but for that, we have to know a particular fact (`Goldbach's Conjecture`) :-\n",
    "\n",
    "** Every even number can be represented as sum of 2 prime numbers. **\n",
    "\n",
    "So, using the conjecture, for any even composite number, the answer will be 2.\n",
    "\n",
    "Now we only have to take care of odd composite number.\n",
    "We know that odd number can be decomposed as:-\n",
    "\n",
    "`odd1 = odd2 + even2`.\n",
    "\n",
    "For `even2`, we know that the answer is 2. We need to somehow minimize the breakdown of `odd2`.\n",
    "Now, since we have the freedom of choosing any even number as `even2`, whose breakdown will give 2 prime numbers, we select `even2` in such a way that `odd2` is prime, like `odd2` is say 3, 5, 7, etc...\n",
    "This we can do for any odd composite number. So, for any odd composite, we have answer as 1 + 2 = 3.\n",
    "\n",
    "But there is this edge case of 2 being an even number as well as prime number.\n",
    " \n",
    "Revisiting the equation\n",
    "\n",
    "`odd1 = odd2 + even2`\n",
    "\n",
    "If even2 is 2, then its answer will be 1. And for this specific case, odd2 is simply `odd1 - 2`. If this `odd2` is prime, then our best answer becomes 1 + 1 = 2, better than 3. If `odd2` is `composite`, then its breakdown would be greater than 1 anyway, so no need to further analyse as we are already getting 3 as an answer.\n",
    "\n",
    "So, for odd case as well, we have to check this edge case."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def solve3(n):\n",
    "    \n",
    "    def is_prime(x):\n",
    "        i = 2\n",
    "        while i * i <= x:\n",
    "            if x % i == 0:\n",
    "                return False\n",
    "            i += 1\n",
    "        return True\n",
    "    \n",
    "    if n == 2:\n",
    "        return 1\n",
    "    elif n % 2 == 0:\n",
    "        return 2\n",
    "    elif is_prime(n):\n",
    "        return 1\n",
    "    elif is_prime(n-2):\n",
    "        return 2\n",
    "    else:\n",
    "        return 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "#### Sample Test Case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve3(889786768567)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q4. Given a number N, find the Nth smallest odd-length pallindromic string. String consists of only lowercase alphabets. For string of same length, order is determined by lexicographical ordering.\n",
    "\n",
    "Given test cases which will clarify the question :-\n",
    "\n",
    "| Input | Output |\n",
    "| ----------- | --------- |\n",
    "| 1    | a   |\n",
    "| 26        | z    |\n",
    "| 27        | aaa    |\n",
    "| 702        | zzz    |\n",
    "| 703        | aaaaa    |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Breakdown"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, basically we are given a serial number and we have to find the string corresponding to that position.\n",
    "\n",
    "\n",
    "There would be 26 strings of length 1, 26 x 26(676) strings of length 3, 26 x 26 x 26 (17576) strings of length 5 and so on...\n",
    "\n",
    "**1.**\n",
    "\n",
    "We can use this knowledge to find the length of Nth string(say length is L). Like, \n",
    "\n",
    "[1, 26] range correspond to strings of length 1 (2 x (1) - 1)\n",
    "\n",
    "[26 + 1, 26 + 26 x 26] range correspond to strings of length 3 (2 x (2) - 1)\n",
    "\n",
    "[26 + 26 x 26 + 1, 26 + 26 x 26 + 26 x 26 x 26] range correspond to strings of length 5 (2 x (3) - 1), and so on....\n",
    "\n",
    "\n",
    "\n",
    "**2.**\n",
    "\n",
    "Also, we can find the position of Nth string in length L(say position is P). Like, \n",
    "\n",
    "N = 30, then we know that it lies in [26 + 1, 26 + 26 x 26] range. So, length of string is 3.\n",
    "Now, 27 is position 1, so 30 is 30 - 27 + 1 = 4th position. (Simply subtract from N, the lower bound of the range it belongs to and then add 1). So L = 3 and P = 4.\n",
    "\n",
    "\n",
    "**3.**\n",
    "\n",
    "Now basically we have to start with the first string of length L and increment it to get to string at position P.\n",
    "Since we already start from the 1st string, we need to further increment (P-1) steps to get to our desired string.\n",
    "\n",
    "Say L = 5 and P = 200.\n",
    "\n",
    "String(of L = 5) at P = 1 is 'aaaaa'. Now, we need to increment it (200 - 1) steps to get to our answer.\n",
    "\n",
    "Since the string is a pallindrome, its enough to operate only on half of the string and later duplicate it before returning.\n",
    "\n",
    "So, we operate on 'aaa' (right half) to increment it by 199.\n",
    "\n",
    "Now, the right half of the string at increment_by 1  would be 'baa'.\n",
    "Similarly, for increment_by 2, we have 'caa'.\n",
    "\n",
    "We observe that the 1st character of this string increases with every position increase.\n",
    "for increment_by 25, we have 'zaa'.\n",
    "for increment_by 26, we have 'aba'.\n",
    "\n",
    "So, at 26th increment, the 1st character rolls back to 'a' again. This can be simulated by a modulus by 26 operation.\n",
    "Now, the 2nd character increments a single unit for every 26 increment in position.\n",
    "So, we have to find number of multiples of 26 within 199, which could be found by (199 // 26) (quotient of division).\n",
    "This will give the number of units by which the 2nd character will increment. Now, again 2nd character will also wrap at each 26th increment. So, use mod 26.\n",
    "\n",
    "Similarly, 3rd character increments a single unit for every 26 x 26 increment in position.\n",
    "\n",
    "So, we have to find number of multiples of 26 x 26 in 199, given by 199 // (26 x 26), and so on...\n",
    "\n",
    "So, we continue in above mentioned manner till we have incremented by 199."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve4(N):\n",
    "    def calc_length_and_pos(n):\n",
    "        i = 1\n",
    "        lower_bound = 1\n",
    "        upper_bound = 26\n",
    "        width = 26\n",
    "        while n > upper_bound:\n",
    "            i += 1\n",
    "            width *= 26\n",
    "            lower_bound = upper_bound + 1\n",
    "            upper_bound += width\n",
    "        return (2 * i - 1, n - lower_bound + 1)\n",
    "    \n",
    "    str_len, pos = calc_length_and_pos(N)\n",
    "    right_half_len = str_len // 2 + 1\n",
    "    right_half_str = ['a'] * right_half_len\n",
    "    \n",
    "    pos, i = pos - 1, 0\n",
    "    while pos:\n",
    "        right_half_str[i] = chr( ord(right_half_str[i]) + pos % 26)\n",
    "        pos = pos // 26\n",
    "        i += 1\n",
    "    return ''.join(right_half_str[1:][::-1] + right_half_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'zzzzzzz'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve4(26 + 26 ** 2  + 26 ** 3 + 26 ** 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}