Modify array by removing (arr[i] + arr[i + 1])th element exactly K times

Given an array arr[] consisting of first N natural numbers, where arr[i] = i ( 1-based indexing ) and a positive integer K, the task is to print the array arr[] obtained after removing every (arr[i] + arr[i + 1])^th element from the array in every i^th operation exactly K times.

Examples:

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}, K = 2
Output: 1 2 4 5 7
Explanation:
Initially, the array arr[] is {1, 2, 3, 4, 5, 6, 7, 8}.
Operation 1: Delete every (A[1] + A[2])^th element, i.e., every 3^rd element from the array arr[]. Now the array modifies to {1, 2, 4, 5, 7, 8}.
Operation 2: Delete every (A[2] + A[3])^th element, i.e., every 6^th element from the array arr[]. Now the array modifies to {1, 2, 4, 5, 7}.
After performing the above operations, the array obtained is {1, 2, 4, 5, 7}.

Input: N = 10, K = 3
Output: 1 2 4 5 7 10

Approach: The given problem can be solved by performing the given operation exactly K times by deleting every (arr[i] + arr[i + 1])^th term from the array in every i^th operation. Follow the steps below to solve the problem:

• Iterate over the range [0, K – 1] using the variable i, and perform the following steps:
  • Initialize an auxiliary array B[] to stores the elements of the array arr[] after each deletion operation.
  • Traverse the given array arr[] and if the current index is not divisible by the value (arr[i] + arr[i + 1]) then insert that element in the array B[].
  • After the above steps, insert all the elements of the array B[] in the array arr[].
• After completing the above steps, print the array arr[] as the resultant array.

Below is the implementation of the above approach:

Python3

def removeEveryKth(l, k):          for i in range(0, len(l)):                                    if i % k == 0:             l[i] = 0                  arr = [0]            for i in range(1, len(l)):                                      if l[i] != 0:             arr.append(l[i])                  return arr    def printArray(l):               for i in range(1, len(l)):         print(l[i], end =" ")        print()    def printSequence(n, k):             l = [int(i) for i in range(0, n + 1)]        x = 1             for i in range(0, k):                              p = l[x] + l[x + 1]                              l = removeEveryKth(l, p)                                      x += 1                 printArray(l)    N = 8 K = 2    printSequence(N, K)

Output:

1 2 4 5 7

Time Complexity: O(N*K)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets