Given an array arr[] consisting of N integers, read every element of the array one by one and perform the following operations:
- If the current element arr[i] had previously occurred in the array, increase its first occurrence by K.
- Otherwise, insert arr[i] into the sequence
The task is to print the final sequence of integers obtained by performing the above operations
Examples:
Input: arr[] = {1, 2, 3, 2, 3}, K = 1
Output: [1, 4, 3, 2, 3]
Explanation:Arrival : 1
Since 1 is the first element in the stream, simply insert it into the solution.
Therefore, b[] = [1]Arrival: 2
Since 2 is not existing in the array, simply insert it into the solution.
Therefore, b[] = [1, 2]Arrival: 3
Since 3 is not existing in the array, simply insert it into the solution.
Therefore, b[] = [1, 2, 3]Arrival: 2
Since 2 already exists, increasing its first occurrence by K(=1)modifies the array b[] to [1, 3, 3, 2]Arrival: 3
Since 3 already exists, increasing its first occurrence by K(=1)modifies the array b[] to [1, 4, 3, 2, 3]Input: arr[] = {1, 4, 1, 1, 4}, K = 6
Output: [7, 10, 7, 1, 4]
Naive Approach: The simplest approach to solve the problem is to traverse the array, and for every array element arr[i], traverse in the range [0, i – 1] to check if arr[i] is already present in the array or not. If found to be true, increase the first occurrence of arr[i] by K.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using Hashing. Follow the steps below to solve the problem:
- Traverse the array and store the occurrence of every array element in a Map paired with the index of its occurrence in increasing order.
- If arr[i] is found to be already present in the Map, remove the first occurrence of arr[i] from the Map. Insert that index paired with arr[i] + K as the key back into the Map.
- Repeat the above steps for all array elements. Once, the entire array is traversed, obtain the sequence of integers from the Map and print the final sequence.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Print the required final sequencevoid printSequence(vector<int>& A,                   int n, int k){    // Stores the array element-index pairs    unordered_map<int, set<int> > mp;Â
    // Stores the required sequence    vector<int> sol;Â
    // Insert all array elements    for (int x : A)        sol.push_back(x);Â
    for (int i = 0; i < n; i++) {        // If current element has        // not occurred previously        if (mp.find(sol[i]) == mp.end()            || mp[sol[i]].size() == 0) {            mp[sol[i]].insert(i);        }Â
        // Otherwise        else {Â
            // Iterator to the first index            // containing sol[i]            auto idxx = mp[sol[i]].begin();Â
            int idx = *idxx;Â
            // Remove that occurrence            mp[sol[i]].erase(idxx);Â
            // Increment by K            sol[idx] += k;Â
            // Insert the incremented            // element at that index            mp[sol[idx]].insert(idx);            mp[sol[i]].insert(i);        }    }Â
    // Print the final sequence    for (int x : sol) {        cout << x << " ";    }}Â
// Driver Codeint main(){Â Â Â Â int N = 5;Â Â Â Â int K = 6;Â Â Â Â vector<int> A = { 1, 4, 1, 1, 4 };Â Â Â Â printSequence(A, N, K);} |
Java
// Java Program to implement the above approachimport java.util.*;Â
public class Main {    // Driver Code    public static void main(String[] args)    {        int N = 5;        int K = 6;        int[] A = { 1, 4, 1, 1, 4 };        printSequence(A, N, K);    }Â
    // Print the required final sequence    public static void printSequence(int[] A, int n, int k)    {        // Stores the array element-index pairs        HashMap<Integer, ArrayList<Integer> > mp            = new HashMap<>();Â
        // Stores the required sequence        ArrayList<Integer> sol = new ArrayList<>();Â
        // Insert all array elements        for (int x : A) {            sol.add(x);        }        for (int i = 0; i < n; i++) {            // If current element has            // not occurred previously            if (!mp.containsKey(sol.get(i))                || mp.get(sol.get(i)).size() == 0) {                mp.put(sol.get(i),                       new ArrayList<>(Arrays.asList(i)));            }            // Otherwise            else {                // first index containing sol[i]                int idx = mp.get(sol.get(i)).get(0);Â
                // Remove that occurrence                mp.get(sol.get(i)).remove((Integer)idx);Â
                // Increment by K                sol.set(idx, sol.get(idx) + k);Â
                // Insert the incremented                // element at that index                mp.putIfAbsent(                    sol.get(idx),                    new ArrayList<>(Arrays.asList()));                mp.get(sol.get(idx)).add((Integer)idx);Â
                mp.putIfAbsent(                    sol.get(i),                    new ArrayList<>(Arrays.asList()));                mp.get(sol.get(i)).add((Integer)i);            }        }        // Print the final sequence        for (int x : sol) {            System.out.print(x + " ");        }    }}Â
// This code is contributed by Tapesh (tapeshdua420) |
Python3
# Python3 Program to implement the above approachÂ
import collectionsÂ
def printSequence(A, n, k):    # Stores the array element-index pairs    mp = collections.defaultdict(set)Â
    # Stores the required sequence    sol = []Â
    # Insert all array elements    for x in A:        sol.append(x)Â
    for i in range(n):        # If current element has not occurred previously        if sol[i] not in mp or len(mp[sol[i]]) == 0:            mp[sol[i]].add(i)        # Otherwise        else:            # Get the first index containing sol[i]            idx = mp[sol[i]].pop()Â
            # Increment by K            sol[idx] += kÂ
            # Insert the incremented element at that index            mp[sol[idx]].add(idx)            mp[sol[i]].add(i)Â
    # Print the final sequence    print(" ".join(map(str, sol)))Â
# Driver CodeN = 5K = 6A = [1, 4, 1, 1, 4]printSequence(A, N, K) |
C#
using System;using System.Collections.Generic;Â
class Program {Â Â static void Main(string[] args) {Â Â Â Â int N = 5;Â Â Â Â int K = 6;Â Â Â Â List<int> A = new List<int> { 1, 4, 1, 1, 4 };Â Â Â Â printSequence(A, N, K);Â Â }Â
  static void printSequence(List<int> A, int n, int k) {    // Stores the array element-index pairs    Dictionary<int, HashSet<int>> mp = new Dictionary<int, HashSet<int>>();Â
    // Stores the required sequence    List<int> sol = new List<int>();Â
    // Insert all array elements    foreach (int x in A)      sol.Add(x);Â
    for (int i = 0; i < n; i++) {      // If current element has not occurred previously      if (!mp.ContainsKey(sol[i]) || mp[sol[i]].Count == 0) {        mp[sol[i]] = new HashSet<int>();        mp[sol[i]].Add(i);      }Â
      // Otherwise      else {        // Iterator to the first index containing sol[i]        var idxx = mp[sol[i]].GetEnumerator();        idxx.MoveNext();        int idx = idxx.Current;Â
        // Remove that occurrence        mp[sol[i]].Remove(idx);Â
        // Increment by K        sol[idx] += k;Â
        // Insert the incremented element at that index        if (!mp.ContainsKey(sol[idx])) {          mp[sol[idx]] = new HashSet<int>();        }        mp[sol[idx]].Add(idx);        mp[sol[i]].Add(i);      }    }Â
    // Print the final sequence    foreach (int x in sol) {      Console.Write(x + " ");    }  }} |
Javascript
<script>Â
// Javascript program to implement// the above approachÂ
// Print the required final sequencefunction printSequence(A, n, k){         // Stores the array element-index pairs    var mp = new Map();Â
    // Stores the required sequence    var sol = [];Â
    // Insert all array elements    A.forEach(x => {        sol.push(x);    });Â
    for(var i = 0; i < n; i++)     {                 // If current element has        // not occurred previously        if (!mp.has(sol[i]) ||              mp.get(sol[i]).size == 0)         {            var tmp = new Set();            tmp.add(i)            mp.set(sol[i],tmp)        }Â
        // Otherwise        else        {                         // Iterator to the first index            // containing sol[i]            var idxx = [...mp.get(sol[i])].sort(                (a, b) => a - b)[0];Â
            var idx = idxx;Â
            // Remove that occurrence            var x = mp.get(sol[i]);            x.delete(idxx);            mp.set(sol[i], x);Â
            // Increment by K            sol[idx] += k;Â
            // Insert the incremented            // element at that index            if (!mp.has(sol[idx]))                mp.set(sol[idx], new Set())                             x = mp.get(sol[idx]);            x.add(idx);            mp.set(sol[idx], x);Â
            x = mp.get(sol[i]);            x.add(i);            mp.set(sol[i], x);        }    }Â
    // Print the final sequence    sol.forEach(x => {        document.write(x + " ");    });}Â
// Driver Codevar N = 5;var K = 6;var A = [ 1, 4, 1, 1, 4 ];Â
printSequence(A, N, K);Â
// This code is contributed by importantlyÂ
</script> |
Output:Â
7 10 7 1 4
Â
Time Complexity: O(N)
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!
… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/modify-given-array-by-incrementing-first-occurrence-of-every-element-by-k/ […]