Sum of absolute differences of indices of occurrences of each array element | Set 2

  

import java.util.*;

  

class GFG {

  

    

    

    

    static class pair {

        int count, prevIndex;

  

        

        pair(int count, int prevIndex)

        {

            this.count = count;

            this.prevIndex = prevIndex;

        }

    }

  

    

    

    

    static void findSum(int[] arr, int n)

    {

        

        

        Map<Integer, pair> map = new HashMap<>();

  

        

        

        int[] left = new int[n];

        int[] right = new int[n];

  

        

        for (int i = 0; i < n; i++) {

  

            

            

            if (!map.containsKey(arr[i])) {

  

                

                

                

                left[i] = 0;

                map.put(arr[i], new pair(1, i));

            }

  

            

            

            else {

                pair tmp = map.get(arr[i]);

                left[i] = (tmp.count)

                              * (i - tmp.prevIndex)

                          + left[tmp.prevIndex];

                map.put(

                    arr[i], new pair(

                                tmp.count + 1, i));

            }

        }

  

        

        

        map.clear();

  

        

        

        for (int i = n - 1; i >= 0; i--) {

  

            

            

            if (!map.containsKey(arr[i])) {

  

                

                

                

                right[i] = 0;

                map.put(arr[i], new pair(1, i));

            }

  

            

            

            else {

  

                pair tmp = map.get(arr[i]);

                right[i]

                    = (tmp.count)

                          * (Math.abs(i - tmp.prevIndex))

                      + right[tmp.prevIndex];

  

                map.put(

                    arr[i], new pair(

                                tmp.count + 1, i));

            }

        }

  

        

        

        

        for (int i = 0; i < n; i++)

            System.out.print(

                left[i] + right[i] + " ");

    }

  

    

    public static void main(String[] args)

    {

        int[] arr = { 1, 3, 1, 1, 2 };

        int N = arr.length;

        findSum(arr, N);

    }

}

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets