{"id":989,"date":"2020-06-10T09:23:41","date_gmt":"2020-06-10T09:23:41","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=989"},"modified":"2022-04-01T09:53:57","modified_gmt":"2022-04-01T09:53:57","slug":"sum-of-sequence","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/sum-of-sequence\/","title":{"rendered":"Sum of Sequence"},"content":{"rendered":"

\"\"<\/p>\n

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

Collatz conjecture<\/p>\n<\/blockquote>\n

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

Easy<\/p>\n<\/blockquote>\n

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

Given a positive number N<\/code>, write a recursive function and sum all the number until N<\/code> reaches to 1<\/code> after performing the following two operations :<\/p>\n

    \n
  1. If N<\/code> is even, then N<\/code> =<\/code> N\/2<\/code><\/li>\n<\/ol>\n<\/blockquote>\n
      \n
    1. If N<\/code> is odd, then N<\/code> =<\/code> 3*N+1<\/code><\/li>\n<\/ol>\n

      NOTE<\/strong>:<\/p>\n

      \n
        \n
      1. \n

        Sum of all number can be large, so print the answer with modulo (10^9+7)<\/code><\/p>\n<\/li>\n

      2. \n

        It is guaranted that N<\/code> will become 1<\/code> at some point.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n

        For Example :<\/h4>\n
        Input: N = 5\n\nOutput: 36\n\nExplanation:\n\nThe sequence will be [5, 16, 8, 4, 2, 1]\n\n5 is odd so N becomes 5*3 + 1 = 16 \nsum becomes 5 + 16 = 21\n\n16 is even so N becomes 16\/2 = 8 \nsum becomes  21 + 8 = 29\n\n8 is even so N becomes 8\/2 = 4 \nsum becomes  29 + 4 = 33\n\n4 is even so N becomes 4\/2 = 2 \nsum becomes  33 + 2 = 35\n\n2 is even so N becomes 2\/2 = 1 \nsum becomes  35 + 1 = 36\n\nN becomes 1 , so return sum = 36<\/code><\/pre>\n
        <\/strong><\/u><\/a><\/p>\n
        Do You Know?<\/em><\/strong><\/p>\n
        \n
        This problem is known as Collatz conjecture<\/a> and it is an open problem with unknown Time Complexity<\/code>. <\/p>\n<\/blockquote>\n
        SOLVING APPROACH:<\/h3>\n
        \n
          \n
        1. \n
          Initialize a Sum<\/code> variable as 0<\/code> and pass it to the recursive function.  <\/p>\n<\/li>\n
        2. \n
          Check if the value of N<\/code> is Even<\/code> or Odd<\/code>. If Even<\/code>, change Sum<\/code> to Sum<\/code> + current-value-of-N<\/code> and reduce N<\/code> to N\/2<\/code>, and pass both values to the recursive function.<\/p>\n<\/li>\n
        3. \n
          If N<\/code> is odd, change Sum<\/code> to Sum<\/code> + current-value-of-N<\/code> and increment N<\/code> by N*3 + 1<\/code>, and pass these values to the recursive function.<\/p>\n<\/li>\n
        4. \n
          If at any point N<\/code> becomes 1<\/code>, return the  Sum<\/code> + current-value-of-N<\/code> i.e. Sum<\/code> + 1<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
          SOLUTIONS:<\/h3>\n
          \t\t\t\t\t\t