 Assignment 1 - Arrays.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "124776f0",
   "metadata": {},
   "source": [
    "# Assignment 1 - Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12ef9c8f",
   "metadata": {},
   "source": [
    " **Q1.** Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.\n",
    "\n",
    "You may assume that each input would have exactly one solution, and you may not use the same element twice.\n",
    "\n",
    "You can return the answer in any order.\n",
    "\n",
    "**Example:**\n",
    "Input: nums = [2,7,11,15], target = 9\n",
    "Output0 [0,1]\n",
    "\n",
    "**Explanation:** Because nums[0] + nums[1] == 9, we return [0, 1]\n",
    "\n",
    "</aside>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a0dd444e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1]\n"
     ]
    }
   ],
   "source": [
    "def twoSum(nums, target):\n",
    "    num_dict = {}\n",
    "    for i, num in enumerate(nums):\n",
    "        complement = target - num\n",
    "        if complement in num_dict:\n",
    "            return [num_dict[complement], i]\n",
    "        num_dict[num] = i\n",
    "    return []\n",
    "\n",
    "\n",
    "nums = [2, 7, 11, 15]\n",
    "target = 9\n",
    "result = twoSum(nums, target)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "226d3523",
   "metadata": {},
   "source": [
    "**Q2.** Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.\n",
    "\n",
    "Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:\n",
    "\n",
    "- Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.\n",
    "- Return k.\n",
    "\n",
    "**Example :**\n",
    "Input: nums = [3,2,2,3], val = 3\n",
    "Output: 2, nums = [2,2,_*,_*]\n",
    "\n",
    "**Explanation:** Your function should return k = 2, with the first two elements of nums being 2. It does not matter what you leave beyond the returned k (hence they are underscores)[\n",
    "\n",
    "</aside>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5c2d600e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 2, 2, 3]\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "def removeElement(nums, val):\n",
    "    k = 0  # number of elements not equal to val\n",
    "\n",
    "    for i in range(len(nums)):\n",
    "        if nums[i] != val:\n",
    "            nums[k] = nums[i]\n",
    "            k += 1\n",
    "\n",
    "    return k\n",
    "def removeElement(nums, val):\n",
    "    k = 0  # number of elements not equal to val\n",
    "\n",
    "    for i in range(len(nums)):\n",
    "        if nums[i] != val:\n",
    "            nums[k] = nums[i]\n",
    "            k += 1\n",
    "\n",
    "    return k\n",
    "nums = [3,2,2,3] #Given\n",
    "val = 3 #Given\n",
    "\n",
    "result = removeElement(nums, val)\n",
    "print(nums)   \n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec43637b",
   "metadata": {},
   "source": [
    "**Q3.** Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.\n",
    "\n",
    "You must write an algorithm with O(log n) runtime complexity.\n",
    "\n",
    "**Example 1:**\n",
    "Input: nums = [1,3,5,6], target = 5\n",
    "\n",
    "Output: 2\n",
    "\n",
    "</aside>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b7d5e20e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search_index(nums, target):\n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "\n",
    "    while left <= right:\n",
    "        mid = (left + right) // 2\n",
    "        \n",
    "        if nums[mid] == target:\n",
    "            return mid\n",
    "        elif nums[mid] < target:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    \n",
    "    return left\n",
    "nums = [1,3,5,6] #Given\n",
    "target = 5 #Given\n",
    "\n",
    "search_index(nums,target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "657a4620",
   "metadata": {},
   "source": [
    "**Q4.** You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.\n",
    "\n",
    "Increment the large integer by one and return the resulting array of digits.\n",
    "\n",
    "**Example 1:**\n",
    "Input: digits = [1,2,3]\n",
    "Output: [1,2,4]\n",
    "\n",
    "**Explanation:** The array represents the integer 123.\n",
    "\n",
    "Incrementing by one gives 123 + 1 = 124.\n",
    "Thus, the result should be [1,2,4].\n",
    "\n",
    "</aside>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5d0b5bf4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def increment_one(digits):\n",
    "    n = len(digits)\n",
    "    carry = 1\n",
    "    \n",
    "    for i in range(n-1, -1, -1):\n",
    "        digits[i] += carry\n",
    "        \n",
    "        if digits[i] < 10:\n",
    "            carry = 0\n",
    "            break\n",
    "        \n",
    "        digits[i] %= 10\n",
    "    \n",
    "    if carry == 1:\n",
    "        digits.insert(0, 1)\n",
    "    \n",
    "    return digits\n",
    "digits = [1,2,3] #Given\n",
    "\n",
    "increment_one(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5082d31",
   "metadata": {},
   "source": [
    " **Q5.** You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.\n",
    "\n",
    "Merge nums1 and nums2 into a single array sorted in non-decreasing order.\n",
    "\n",
    "The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.\n",
    "\n",
    "**Example 1:**\n",
    "Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3\n",
    "Output: [1,2,2,3,5,6]\n",
    "\n",
    "**Explanation:** The arrays we are merging are [1,2,3] and [2,5,6].\n",
    "The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.\n",
    "\n",
    "</aside>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "16c7967b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 3, 5, 6]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def merge(nums1, m, nums2, n):\n",
    "    p1 = m - 1  # Pointer for nums1\n",
    "    p2 = n - 1  # Pointer for nums2\n",
    "    p = m + n - 1  # Pointer for the merged array\n",
    "    \n",
    "    while p1 >= 0 and p2 >= 0:\n",
    "        if nums1[p1] > nums2[p2]:\n",
    "            nums1[p] = nums1[p1]\n",
    "            p1 -= 1\n",
    "        else:\n",
    "            nums1[p] = nums2[p2]\n",
    "            p2 -= 1\n",
    "        p -= 1\n",
    "    \n",
    "    # If there are remaining elements in nums2, copy them to nums1\n",
    "    while p2 >= 0:\n",
    "        nums1[p] = nums2[p2]\n",
    "        p2 -= 1\n",
    "        p -= 1\n",
    "\n",
    "    return nums1\n",
    "nums1 = [1,2,3,0,0,0] #Given\n",
    "m = 3 #Given\n",
    "nums2 = [2,5,6] #Given\n",
    "n = 3 #Given\n",
    "\n",
    "merge(nums1, m, nums2, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af3fb054",
   "metadata": {},
   "source": [
    "**Q6.** Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.\n",
    "\n",
    "**Example 1:**\n",
    "Input: nums = [1,2,3,1]\n",
    "\n",
    "Output: true\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "a5c87b6a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def check_duplicates(nums):\n",
    "    num_set = set()\n",
    "\n",
    "    for num in nums:\n",
    "        if num in num_set:\n",
    "            return True\n",
    "        else:\n",
    "            num_set.add(num)\n",
    "\n",
    "    return False\n",
    "\n",
    "\n",
    "nums = [1, 2, 3, 1]\n",
    "result = check_duplicates(nums)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "596e5fdd",
   "metadata": {},
   "source": [
    "**Q7.** Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the nonzero elements.\n",
    "\n",
    "Note that you must do this in-place without making a copy of the array.\n",
    "\n",
    "**Example 1:**\n",
    "Input: nums = [0,1,0,3,12]\n",
    "Output: [1,3,12,0,0]\n",
    "\n",
    "</aside>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "678f673d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 12, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "def Sort_Zeroes(nums):\n",
    "    left = 0 \n",
    "\n",
    "    for right in range(len(nums)):\n",
    "        if nums[right] != 0:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "\n",
    "    return nums\n",
    "\n",
    "nums = [0, 1, 0, 3, 12]\n",
    "result = Sort_Zeroes(nums)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e68df4f",
   "metadata": {},
   "source": [
    "**Q8.** You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.\n",
    "\n",
    "You are given an integer array nums representing the data status of this set after the error.\n",
    "\n",
    "Find the number that occurs twice and the number that is missing and return them in the form of an array.\n",
    "\n",
    "**Example 1:**\n",
    "Input: nums = [1,2,2,4]\n",
    "Output: [2,3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "78de7086",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3]\n"
     ]
    }
   ],
   "source": [
    "def duplicate_detector(nums):\n",
    "    n = len(nums)\n",
    "    num_set = set()\n",
    "    duplicate = 0\n",
    "    missing = 0\n",
    "\n",
    "   \n",
    "    for num in nums:\n",
    "        if num in num_set:\n",
    "            duplicate = num\n",
    "        else:\n",
    "            num_set.add(num)\n",
    "\n",
    "   \n",
    "    for i in range(1, n + 1):\n",
    "        if i not in num_set:\n",
    "            missing = i\n",
    "            break\n",
    "\n",
    "    return [duplicate, missing]\n",
    "\n",
    "nums = [1, 2, 2, 4]\n",
    "result = duplicate_detector(nums)\n",
    "print(result)"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}