{"id":403,"date":"2020-06-10T10:41:17","date_gmt":"2020-06-10T10:41:17","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=403"},"modified":"2022-03-28T00:37:49","modified_gmt":"2022-03-28T00:37:49","slug":"arithmetic-progression","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/arithmetic-progression\/","title":{"rendered":"Arithmetic Progression"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Hashing, Basic Mathematics<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array of N<\/code> integers, print the value of all those elements, whose indexes form an increasing Arithmetic Progression<\/code> along with the difference in Arithmetic Progression<\/code>. If an element occurs single time then print 0<\/code> as difference.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input: \n\nN = 8\nA[] = [4, 2, 4, 3, 4, 2, 4, 5]\n\nOutput: \n\n4\n2 4\n3 0 \n4 2\n5 0\n\nExplanation:\n\n2 is present at index 1 and 5 which forms an A.P. with common difference 4 \n\n3 is present only at index 3 which is again an A.P. with common difference 0\n\n4 is present at index 0, 2, 4, and 6 which forms an A.P. with common difference 2\n\n5 is present only at index 7 which is again an A.P. with common difference 0<\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. \n
    It can be easily solved in Linear Time Complexity<\/code> i.e. O(N)<\/code> but taking additional O(N)<\/code> space.<\/p>\n<\/li>\n
  2. \n
    Traverse the array and keep putting the elements into a set<\/code>.
    \nA set<\/code> is a data structure that contains unique elements.<\/p>\n<\/li>\n
  3. \n
    Maintain two different arrays for difference value<\/code> and last value<\/code> of an element and keep updating them.<\/p>\n<\/li>\n
  4. \n
    If the updated difference value<\/code> does not matches the old value, this implies that the indices of this element are not in Arithmetic Progression<\/code>. Therefore remove the element from the set.<\/p>\n<\/li>\n
  5. \n
    Finally print the elements and their difference value<\/code> from the set.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    ILLUSTRATION:<\/h4>\n
    A[] = [4, 2, 4, 3, 4]\n\ni = 0\nset = { }\n\nA[0] = 4 is not present in set, insert it\nset = {4}\ndiff[4] = 0\nlast_index[4] = i = 0\ni++;\n\ni = 1\nA[1] = 2 is not present in set, insert it\nset = {2, 4}\ndiff[2] = 0\nlast_index[2] = i =  1\ni++;\n\ni = 2\nA[2] = 4 is present in set, update last_index and difference\ndiff[4] = i - last_index[4] = 2 - 0 = 2\nlast_index[4] = i =  2\ni++;\n\ni = 3\nA[3] = 3 is not present in set, insert it\nset = {2, 3, 4}\ndiff[3] = 0\nlast_index[3] = i = 3\ni++ ;\n\ni = 4\nA[4] = 4 is present in set, update last_index and difference\n(if updated diff is not equal to previous diff, erase this element)\ndiff[4] = i - last_index[4] = 4 - 2 = 2\nlast_index[4] = i = 4\n\nNow print all elements of set along with their differences\n\nset = {2, 3, 4}\n\n3   (size of set)\n2 0 (diff[2])\n3 0 (diff[3])\n4 2 (diff[4])<\/code><\/pre>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t