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 ith 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 3rd 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 6th 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 ith 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:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to modify array by removing// every K-th element from the arrayvector<int> removeEveryKth(vector<int> l, int k){ for (int i = 0; i < l.size(); i++) { // Check if current element // is the k-th element if (i % k == 0) l[i] = 0; } // Stores the elements after // removing every kth element vector<int> arr; arr.push_back(0); for (int i = 1; i < l.size(); i++) { // Append the current element // if it is not k-th element if (l[i] != 0) arr.push_back(l[i]); } // Return the new array after // removing every k-th element return arr;}// Function to print the arrayvoid printArray(vector<int> l){ // Traverse the array l[] for (int i = 1; i < l.size(); i++) cout << l[i] << " "; cout << endl;}// Function to print the array after// performing the given operations// exactly k timesvoid printSequence(int n, int k){ // Store first N natural numbers vector<int> l(n+1); for (int i = 0; i < n + 1; i++) l[i]=i; int x = 1; // Iterate over the range [0, k-1] for (int i = 0; i < k; i++) { // Store sums of the two // consecutive terms int p = l[x] + l[x + 1]; // Remove every p-th // element from the array l = removeEveryKth(l, p); // Increment x by 1 for // the next iteration x += 1; } // Print the resultant array printArray(l);}// Driver Codeint main(){ // Given arrays int N = 8; int K = 2; //Function Call printSequence(N, K);}// This code is contributed by mohit kumar 29 |
Java
// java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to modify array by removing // every K-th element from the array static int[] removeEveryKth(int l[], int k) { for (int i = 0; i < l.length; i++) { // Check if current element // is the k-th element if (i % k == 0) l[i] = 0; } // Stores the elements after // removing every kth element ArrayList<Integer> list = new ArrayList<>(); list.add(0); for (int i = 1; i < l.length; i++) { // Append the current element // if it is not k-th element if (l[i] != 0) list.add(l[i]); } // Return the new array after // removing every k-th element return list.stream().mapToInt(i -> i).toArray(); } // Function to print the array static void printArray(int l[]) { // Traverse the array l[] for (int i = 1; i < l.length; i++) System.out.print(l[i] + " "); System.out.println(); } // Function to print the array after // performing the given operations // exactly k times static void printSequence(int n, int k) { // Store first N natural numbers int l[] = new int[n + 1]; for (int i = 0; i < n + 1; i++) l[i] = i; int x = 1; // Iterate over the range [0, k-1] for (int i = 0; i < k; i++) { // Store sums of the two // consecutive terms int p = l[x] + l[x + 1]; // Remove every p-th // element from the array l = removeEveryKth(l, p); // Increment x by 1 for // the next iteration x += 1; } // Print the resultant array printArray(l); } // Driver Code public static void main(String[] args) { // Given arrays int N = 8; int K = 2; // Function Call printSequence(N, K); }}// This code is contributed by Kingash. |
Python3
# Python approach for the above approach# Function to modify array by removing# every K-th element from the arraydef removeEveryKth(l, k): for i in range(0, len(l)): # Check if current element # is the k-th element if i % k == 0: l[i] = 0 # Stores the elements after # removing every kth element arr = [0] for i in range(1, len(l)): # Append the current element # if it is not k-th element if l[i] != 0: arr.append(l[i]) # Return the new array after # removing every k-th element return arr# Function to print the arraydef printArray(l): # Traverse the array l[] for i in range(1, len(l)): print(l[i], end =" ") print()# Function to print the array after# performing the given operations# exactly k timesdef printSequence(n, k): # Store first N natural numbers l = [int(i) for i in range(0, n + 1)] x = 1 # Iterate over the range [0, k-1] for i in range(0, k): # Store sums of the two # consecutive terms p = l[x] + l[x + 1] # Remove every p-th # element from the array l = removeEveryKth(l, p) # Increment x by 1 for # the next iteration x += 1 # Print the resultant array printArray(l)# Driver CodeN = 8K = 2# Function CallprintSequence(N, K) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to modify array by removing // every K-th element from the array static List<int> removeEveryKth(List<int> l, int k) { for (int i = 0; i < l.Count; i++) { // Check if current element // is the k-th element if (i % k == 0) l[i] = 0; } // Stores the elements after // removing every kth element List<int> arr = new List<int>(); arr.Add(0); for (int i = 1; i < l.Count; i++) { // Append the current element // if it is not k-th element if (l[i] != 0) arr.Add(l[i]); } // Return the new array after // removing every k-th element return arr; } // Function to print the array static void printArray(List<int> l) { // Traverse the array l[] for (int i = 1; i < l.Count; i++) Console.Write(l[i] + " "); Console.WriteLine(); } // Function to print the array after // performing the given operations // exactly k times static void printSequence(int n, int k) { // Store first N natural numbers List<int> l = new List<int>(); for (int i = 0; i < n + 1; i++) l.Add(i); int x = 1; // Iterate over the range [0, k-1] for (int i = 0; i < k; i++) { // Store sums of the two // consecutive terms int p = l[x] + l[x + 1]; // Remove every p-th // element from the array l = removeEveryKth(l, p); // Increment x by 1 for // the next iteration x += 1; } // Print the resultant array printArray(l); } // Driver Code public static void Main() { // Given arrays int N = 8; int K = 2; // Function Call printSequence(N, K); }}// This code is contributed by ukasp. |
Javascript
<script> // Javascript program for the above approach // Function to modify array by removing // every K-th element from the array function removeEveryKth(l, k) { for (let i = 0; i < l.length; i++) { // Check if current element // is the k-th element if (i % k == 0) l[i] = 0; } // Stores the elements after // removing every kth element let arr = [0]; for (let i = 1; i < l.length; i++) { // Append the current element // if it is not k-th element if (l[i] != 0) arr.push(l[i]); } // Return the new array after // removing every k-th element return arr; } // Function to print the array function printArray(l) { // Traverse the array l[] for (let i = 1; i < l.length; i++) document.write(l[i] + " "); } // Function to print the array after // performing the given operations // exactly k times function printSequence(n, k) { // Store first N natural numbers let l = [0]; for (let i = 0; i < n + 1; i++) l[i] = i; let x = 1; // Iterate over the range [0, k-1] for (let i = 0; i < k; i++) { // Store sums of the two // consecutive terms let p = l[x] + l[x + 1]; // Remove every p-th // element from the array l = removeEveryKth(l, p); // Increment x by 1 for // the next iteration x += 1; } // Print the resultant array printArray(l); } // Driver Code // Given arrays let N = 8; let K = 2; //Function Call printSequence(N, K); // This code is contributed by Hritik </script> |
Output:
1 2 4 5 7
Time Complexity: O(N*K)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
