Concepts Used
Sorting
Difficulty Level
Medium
Problem Statement (Simplified):
For a given array, shift elements to the back of array until you get the minimum value of the whole array, repeat until the whole array is emptied. Find such a total number of steps and print.
See original problem statement here
Test case
Input:
4
8 5 2 3
Output:
7
Explanation:
In the given example [8,5,2,3], the minimum value of bad deed is 2.
 God first looks at the soul having value 8 on it, he sends him to the end of the queue as 8!=2. Updated line  [5,2,3,8].
 God looks at the soul having value 5 on it, he sends him to the end of the queue as 5!=2. Updated line  [2,3,8,5].
 God looks at the soul having value 2 on it, he gives Salvation to this soul because 2==2. Updated line  [3,8,5] and the new minimum value is 3.
 God looks at the soul having value 3 on it, he gives salvation to this soul because 3==3. Updated line  [8,5] and the new minimum value is 5.
 God looks at the soul having value 8 on it, he sends him to the end of the queue as 8!=5. Updated line  [5,8].
 God looks at the soul having value 5 on it, he gives salvation to this soul because 5==5. Updated line  [8] and the new minimum value is 8.

God looks at the soul having value 8 on it, he gives Salvation to this soul because 8==8. Updated line  Empty.
Finally, all souls received salvation.
Thus, the total number of times God selects the souls is 7.
Solving Approach :
Bruteforce Approach:
1) We can learn programming online and create a duplicate array of current array and sort it. So, this array will give us the current minimum value in the array.
2) Now we will traverse on our main array until whole elements from a duplicate array are traversed. With every traversal, if the current element is not1
, we add1
to total steps. If the item is the current smallest, we make the element1
, move the pointer of duplicate sorted array to the next element.
3) If we reach the end of our main array, we move the pointer to the first element of the array.
3) After the whole array is traversed, we print the total number of steps.
4) This approach takesO(N^{2})
in the worst case, which is highly inefficient for given constraints.
Efficient Approach:
1) We can solve this problem if we know all positions of any element in the array, so we can maintain a set or a 2D array where
row
represents an element in the array, andcolumns
contains indexes at which the number is present.
2) We start from the least value (Minimum value of all elements) of the array to greatest (Maximum value of all elements) value in the array, so that it will be easy to remove and calculate distance easily.
3) We traverse for all indexes of an element, in each traversal we check the farthest position of the element from our current position, where current position changes after every element is traversed completely.
4) If during traversal our ending position crosses the current position, we add the size of the array to solution as the whole array was traversed.
5) Also we add the total number of appearances of the current element to the final answer because deleting each element once also consumes one step.
6) We decrease the final size of the array by a number of appearances of the traversed element as they'll be removed after it's all position are traversed.
7) We apply the same for all elements. In end, we print the final answer.
Example
 Lets assume array
[1,2,3,3,1]
as our array, if we note all its elements with indexes, we can see1
appears at index0
and4
,2
appears at index1
and3
,3
appears only at index2
. If we start from index
0
, and traverse elements from least to greatest, so we'll traverse first for1
, then2
and3
finally. We traverse
1
first, we can see our starting position is0
, but the last value of1
appears at index4
, so our ending position becomes4
. As we never iterated the whole array, we'll add only2
to solution i.e. number of appearances of1
in the array. So the answer becomes2
. After removing
1
our array size becomes52
i.e.3
and our starting position becomes4
. We traverse
2
now, we can see our starting position is4
, but the last value of2
appears at index3
, so our ending position becomes3
. As ending position is smaller than starting position so we add whole array size to solution too because, in this case, we iterated the whole array. Answer becomes2+3
i.e.5
. We'll also add2
to solution i.e. number of appearances of2
in the array. So the answer becomes5+2
i.e.7
. After removing
2
our array size becomes32
i.e.1
and our starting position becomes3
. We traverse
3
now, we can see our starting position is3
, but the last value of3
appears at index2
, so our ending position becomes2
. As ending position is smaller than starting position so we add whole array size to the solution too because, in this case, we iterated the whole array. Answer becomes7+1
i.e.8
. We'll also add1
to solution i.e. number of appearances of1
in the array. So answer becomes8+1
i.e.9
. After removing
1
our array size becomes11
i.e.0
. As the whole array has been iterated and size of the array becomes0
. We stop traversal. Our final answer value is
9
, so we print9
as our answer.Solutions
#include <bits/stdc++.h> using namespace std; int positions[100001][5000]; int ind[100001]={0}; int main() { int n; cin>>n; int startingSouls = n; int arr[n]; for(int i=0; i<n;i++){ cin>>arr[i]; positions[arr[i]][ind[arr[i]]++] = i; } long solution; int curPos; for(int i=0; i<100001; i++){ int endPos = curPos; int worst = 1; for(int j=0; j<ind[i];j++){ int pos = positions[i][j]; int checks = (pos  curPos) % startingSouls; if (checks < 0) { checks += startingSouls; } if (curPos > pos) { solution++; } if (checks > worst) { worst = checks; endPos = pos; } } if (curPos > endPos) { solution += n; }else { solution += ind[i]; } n = ind[i]; curPos = endPos; } cout<<solution<<endl; }import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int startingSouls = n; String[] SoulsStr = br.readLine().split(" "); @SuppressWarnings("unchecked") ArrayList<Integer>[] positions = (ArrayList<Integer>[]) new ArrayList[100001]; for (int i = 0; i < positions.length; i++) { positions[i] = new ArrayList<Integer>(); } for (int i = 0; i < n; i++) { int value = Integer.parseInt(SoulsStr[i]); positions[value].add(i); } long solution = 0; int curPos = 0; for (int i = 1; i < positions.length; i++) { int endPos = curPos; int worst = 1; for (int j = 0; j < positions[i].size(); j++) { int pos = positions[i].get(j); int checks = (pos  curPos) % startingSouls; if (checks < 0) { checks += startingSouls; } if (curPos > pos) { solution++; } if (checks > worst) { worst = checks; endPos = pos; } } if (curPos > endPos) { solution += n; }else { solution += positions[i].size(); } n = positions[i].size(); curPos = endPos; } System.out.println(solution); } }#include <stdio.h> int positions[100001][5000]; int ind[100001]={0}; int main() { int n; scanf("%d",&n); int startingSouls = n; int arr[n]; for(int i=0; i<n;i++){ scanf("%d",&arr[i]); positions[arr[i]][ind[arr[i]]++] = i; } long solution = 0; int curPos = 0; for(int i=0; i<100001; i++){ int endPos = curPos; int worst = 1; for(int j=0; j<ind[i];j++){ int pos = positions[i][j]; int checks = (pos  curPos) % startingSouls; if (checks < 0) { checks += startingSouls; } if (curPos > pos) { solution++; } if (checks > worst) { worst = checks; endPos = pos; } } if (curPos > endPos) { solution += n; }else { solution += ind[i]; } n = ind[i]; curPos = endPos; } printf("%ld\n",solution); }
Space Complexity
O(
1000001
) space is taken to maintain aPosition
Array
.