Largest permutation of elements in the range 1,....,N

In summary: Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse); for(int i = 0; i < arr.Length && k > 0; ++i) if(arr[i] == n) continue; int j = arr.Length -
  • #1
SlurrerOfSpeech
141
11
with at most k swaps. (In other words, like the largest number formed by swapping k digits.)

Example. A=[4,2,3,5,1], k = 1 ---> [5,2,3,4,1]

I'm wondering why my algorithm is failing the test cases which I'm unable to see.

Code:
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    public static void Swap(int[] A, int i1, int i2)
    {
        int temp = A[i1];
        A[i1] = A[i2];
        A[i2] = temp;
    }
    static void Main(String[] args)
    {
        int[] parameters = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int n = parameters[0];
        int k = parameters[1];
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        for(int i = 0; i < arr.Length && k > 0; ++i)
        {
           if(arr[i] == n) 
               continue;
           int j = arr.Length - 1;
           for(; j > i && arr[j] != n; --j);
            Swap(arr,i,j);
            --n;
            --k;
        }
        Console.WriteLine(string.Join(" ", arr));
    }
}
 
Technology news on Phys.org
  • #2
Your algorithm is O(N2). You need to find an O(N) algorithm.
 
  • #3
I think things go wrong when you try to skip a swap.

Edit: no, never mind. I misunderstood.
 
Last edited:
  • #4
D H said:
Your algorithm is O(N2). You need to find an O(N) algorithm.
To make this clear, this is a hacker rank problem. Problem sites such as this focus solely on efficiency in the small, and in the process create rather artificial problems. This is an artificial problem.

As an alternative to beating yourself over the head on those artificial hacker rank problems, try looking into contributing to an existing open source project. There are many active open source projects at github and bitbucket, some of which are begging for help. So help. Along the way, you'll learn about version control, about the project, how to understand a large codebase, how to contribute to it, and how to test your contributions. This is much more worthwhile than solving one dynamic programming problem after another.

That said, dynamic programming comes into play in this problem. (This is an important concept you should learn.) DP oftentimes uses memoization. You haven't done that. You instead have that inner loop, which can be done away with by memoization. You haven't taken full advantage of the artificial nature of the problem, which is that the input sequence is a permutation of the integers between 1 and N (inclusive). Keep track of the indices of the values between 1 to N in an easily build array. Now when you swap, you need to swap index array elements as well as value array elements so that the index array always keeps in sync with the value array.Aside: DYAC, "memoization" is a word! Stop trying to change it to "memorization!"
 
  • Like
Likes Pepper Mint
  • #5
D H said:
That said, dynamic programming comes into play in this problem. (This is an important concept you should learn.) DP oftentimes uses memoization. You haven't done that. You instead have that inner loop, which can be done away with by memoization. You haven't taken full advantage of the artificial nature of the problem, which is that the input sequence is a permutation of the integers between 1 and N (inclusive). Keep track of the indices of the values between 1 to N in an easily build array. Now when you swap, you need to swap index array elements as well as value array elements so that the index array always keeps in sync with the value array.

Ah, I see.

Lemme try this.
 
  • #6
Hmm, this is still failing some of the test cases.

Code:
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    public static void Swap(int[] A, int i1, int i2)
    {
        int temp = A[i1];
        A[i1] = A[i2];
        A[i2] = temp;
    }
    static void Main(String[] args)
    {
        int[] parameters = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int n = parameters[0];
        int k = parameters[1];
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int[] pos = new int[n]; // pos[m-1] is the index of the value m in arr
        for(int i = 0; i < arr.Length; ++i)
        {
            pos[arr[i] - 1] = i;
        }
        for(int i = 0; i < arr.Length && k > 0; ++i, --n)
        {
           if(arr[i] == n)
               continue;
           int j = pos[n - 1];
           Swap(pos,arr[i]-1,n-1);
           Swap(arr,i,j);
           --k;
        }
        Console.WriteLine(string.Join(" ", arr));
    }
}
 
  • #7
SlurrerOfSpeech said:
Hmm, this is still failing some of the test cases.

Code:
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    public static void Swap(int[] A, int i1, int i2)
    {
        int temp = A[i1];
        A[i1] = A[i2];
        A[i2] = temp;
    }
    static void Main(String[] args)
    {
        int[] parameters = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int n = parameters[0];
        int k = parameters[1];
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int[] pos = new int[n]; // pos[m-1] is the index of the value m in arr
        for(int i = 0; i < arr.Length; ++i)
        {
            pos[arr[i] - 1] = i;
        }
        for(int i = 0; i < arr.Length && k > 0; ++i, --n)
        {
           if(arr[i] == n)
               continue;
           int j = pos[n - 1];
           Swap(pos,arr[i]-1,n-1);
           Swap(arr,i,j);
           --k;
        }
        Console.WriteLine(string.Join(" ", arr));
    }
}
1. validate inputs
2. validate returned values from all methods
 
  • #8
The input would be valid. The specs of the problem guarantee that. All the test cases expect for the 3 last ones are passing, and sometimes the failing ones fail with a Runtime Error and other times a Wrong Answer. I think HackerRank's C# engine is screwed up. I changed to Int64 and still getting errors.
 
  • #9
SlurrerOfSpeech said:
The input would be valid. The specs of the problem guarantee that.
The specs might state so but the written code above I mean clearly isn't "guaranteed" to be bug-free.
All the test cases expect for the 3 last ones are passing, and sometimes the failing ones fail with a Runtime Error and other times a Wrong Answer. I think HackerRank's C# engine is screwed up. I changed to Int64 and still getting errors.
A lot of unknown errors related to runtime, it could be your code is accessing an invalid array object, for example. "Wrong Answer" is probably due to an incorrect implementation of your algorithm.
The probability that HackerRank system fails is also present but at least your code needs to be reworked with more guarding snippets to check all methods' returned values. Best practice is for the long road ahead in coding not for passing a pretty simple exercise of likely a test interview with a man-made system.
 
  • #10
If you are assuming no gaps or duplicates, then this seams to be the problem:
Java:
        for(int i = 0; i < arr.Length && k > 0; ++i)
        {
           // if this happens, then n is not decremented
           if(arr[i] == n)
               continue;
           int j = arr.Length - 1;

           // and then if n was not decremented last iteration
           // then n is at arr[i-1], so this loop will not find n, and will only result in j=i
           // so you will waste a swap, swapping arr[i] with itself
           for(; j > i && arr[j] != n; --j);
            Swap(arr,i,j);
            --n;
            --k;
        }

Otherwise, if gaps or duplicates are allowed, then there are more problems
 
  • Like
Likes Pepper Mint

Related to Largest permutation of elements in the range 1,....,N

1. What is the largest permutation of elements in the range 1,....,N?

The largest permutation of elements in the range 1,....,N is the rearrangement of the numbers 1 to N in descending order.

2. How can I find the largest permutation of elements in the range 1,....,N?

To find the largest permutation of elements in the range 1,....,N, you can sort the numbers in descending order using a sorting algorithm such as bubble sort or selection sort.

3. Can there be multiple largest permutations of elements in the range 1,....,N?

No, there can only be one largest permutation of elements in the range 1,....,N. This is because the largest permutation is determined by the numbers 1 to N being arranged in descending order, and there is only one way to do this.

4. What is the time complexity of finding the largest permutation of elements in the range 1,....,N?

The time complexity of finding the largest permutation of elements in the range 1,....,N is O(N), which means it takes linear time to find the largest permutation. This is because the sorting algorithm used to find the largest permutation has a time complexity of O(N).

5. Is the largest permutation of elements in the range 1,....,N always the same for a given N?

Yes, the largest permutation of elements in the range 1,....,N will always be the same for a given N. This is because the largest permutation is determined by the numbers 1 to N being arranged in descending order, and this arrangement will not change for a given N.

Similar threads

  • Programming and Computer Science
Replies
10
Views
1K
  • Programming and Computer Science
Replies
2
Views
851
  • Programming and Computer Science
Replies
6
Views
2K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
3
Views
2K
  • Programming and Computer Science
Replies
8
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
Back
Top