Quality Factor

Last Updated on March 23, 2022 by Ria Pathak

CONCEPTS USED:

Basic Mathematics

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given a magical container such that whenever :-

1. A Red Stone is added to the i^th bag, the quality factor of i to N bags increases by 1.
2. A Black Stone is added to the i^th bag, the quality factor of i to N bags decreases by 1.
   Given an array of N bags, task is to perform minimum no. of operations on the magical container and equalise both the containers.

See original problem statement here

For Example:

Input : N = 5, A[] = [1, 2, 3, 4, 5]

Output : 5 

Explanation : 

Quality factor of given container   [1, 2, 3, 4, 5]
Quality factor of magical container [0, 0, 0, 0, 0]

Adding a Red stone at index 0,
Quality factor of given container   [1, 2, 3, 4, 5]
Quality factor of magical container [1, 1, 1, 1, 1]

Adding a Red stone at index 1,
Quality factor of given container   [1, 2, 3, 4, 5]
Quality factor of magical container [1, 2, 2, 2, 2]

Adding a Red stone at index 2,
Quality factor of given container   [1, 2, 3, 4, 5]
Quality factor of magical container [1, 2, 3, 3, 3]

Adding a Red stone at index 3,
Quality factor of given container   [1, 2, 3, 4, 5]
Quality factor of magical container [1, 2, 3, 4, 4]

Adding a Red stone at index 4,
Quality factor of given container   [1, 2, 3, 4, 5]
Quality factor of magical container [1, 2, 3, 4, 5]

Both containers are equalised by performing 5 operations.

OBSERVATION:

Whenever a stone is added to a bag, it affects all the bags from i to N bags i.e. all bags including the current one and all to the right of it. While the left bags remain unchanged.

Can you now think of something that can be used using this Hint before going to the solution?

SOLVING APPROACH:

1. The approach is to start from the left most side of the array and keep on equalising the elements in both the arrays. Because once we move ahead, our next actions will not disturb the left side of the array.
2. Initialise current and total as 0 and start traversing the array from the left.
3. for every element A[i], the absolute difference between the element and current is the number of operations required to equalise ith element of the Magical container with A[i], keep adding the absolute difference to total. Also update current with A[i].
4. Keep following the same procedure for equalising each and every element.

ILLUSTRATION:

A[] = [1, 2, 3, 2]
Q[] = [0, 0, 0, 0]

count = 0
current = 0

i = 0
count = count + abs(A[i] - current) = 0 + abs(A[0] - 0) = 0 + 1 = 1
current = A[0] = 1
i++ 

i = 1
count = count + abs(A[i] - current) = 1 + abs(A[1] - 1) = 1 + abs(2 - 1) = 2
current = A[1] = 2
i++ 

i = 2
count = count + abs(A[i] - current) = 2 + abs(A[2] - 2) = 2 + abs(3 - 2) = 3
current = A[2] = 3
i++

i = 3
count = count + abs(A[i] - current) = 3 + abs(A[3] - 3) = 3 + abs(2 - 3) = 4
current = A[3] = 2
i++ 

Total operations to be performed are 4.

SOLUTIONS:

#include <stdio.h>

int main()
{
  int n;
  scanf("%d",&n);
  int arr[n];
  for(int i=0;i<n;i++)
    scanf("%d",&arr[i]);
  int current = 0;
  long long moves = 0;
  for(int i=0;i<n;i++)
  {
      moves += abs(arr[i]-current);
      current = arr[i];
  }
  printf("%lld\n",moves);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int n;cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
    cin>>arr[i];
  int current = 0;
  long long moves = 0;
  for(int i=0;i<n;i++)
  {
      moves += abs(arr[i]-current);
      current = arr[i];
  }
  cout<<moves<<"\n";
  return 0;
}

import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int arr[] = new int[n];
    for(int i=0;i<n;i++)
      arr[i] = sc.nextInt();
    int current = 0;
    long moves = 0;
    for(int i=0;i<n;i++)
    {
        moves += Math.abs(arr[i]-current);
        current = arr[i];
    }
    System.out.println(moves);
  }
}

[forminator_quiz id="693"]

This article tried to discuss the concept of Basic Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Basic Mathematics you can check out MYCODE | Competitive Programming.