Salvation of Soul

Last Updated on March 30, 2022 by Ria Pathak

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.

1. 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].
2. 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].
3. 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.
4. 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.
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].
6. 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.

7. 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 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 not -1, we add 1 to total steps. If the item is the current smallest, we make the element -1, 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 takes O(N²) 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 2-D array where row represents an element in the array, and columns 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 see 1 appears at index 0 and 4, 2 appears at index 1 and 3, 3 appears only at index 2.
• If we start from index 0, and traverse elements from least to greatest, so we’ll traverse first for 1, then 2 and 3 finally.
• We traverse 1 first, we can see our starting position is 0, but the last value of 1 appears at index 4, so our ending position becomes 4. As we never iterated the whole array, we’ll add only 2 to solution i.e. number of appearances of 1 in the array. So the answer becomes 2.
• After removing 1 our array size becomes 5-2 i.e. 3 and our starting position becomes 4.
• We traverse 2 now, we can see our starting position is 4, but the last value of 2 appears at index 3, so our ending position becomes 3. 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 becomes 2+3 i.e. 5. We’ll also add 2 to solution i.e. number of appearances of 2 in the array. So the answer becomes 5+2 i.e. 7.
• After removing 2 our array size becomes 3-2 i.e. 1 and our starting position becomes 3.
• We traverse 3 now, we can see our starting position is 3, but the last value of 3 appears at index 2, so our ending position becomes 2. 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 becomes 7+1 i.e. 8. We’ll also add 1 to solution i.e. number of appearances of 1 in the array. So answer becomes 8+1 i.e. 9.
• After removing 1 our array size becomes 1-1 i.e. 0. As the whole array has been iterated and size of the array becomes 0. We stop traversal.
• Our final answer value is 9, so we print 9 as our answer.

Solutions

#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);

}

#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);
    }
}

primes = [0] * 100006

def setPrimes():

	global primes

	for i in range(2, 100006):
		primes[i] = 1

	primes[0] = 0
	primes[1] = 0

	for i in range(2, 100006):

		for j in range(2 * i, 100006, i):
			primes[j] = 0

setPrimes()
for _ in range(int(input())):

	n = int(input())
	sum = 0
	i = 2

	while(n!=0):
		if( primes[i] == 1 ):
			k = i
			odd = 0
			while(k):
				if(primes[k % 10] == 1 and k % 10 != 2):
					odd = 1
					break
				
				k//=10
			
			if(odd == 0):
				sum += i
				n -= 1

		i += 1

	print(sum)

[forminator_quiz id="1352"]

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