RGK
BAN USERIf the array becomes sorted based on just one swap then utmost two elements can be out of order.
Iterate through the array and for each iteration the following condition must hold - elements[i] < elements[i+1]. If this is not the case then we have found the first element that is out of order. Pick the smallest element named elements[j] from the remaining portion of the array such that the index j is greater than i
Swap these two elements and iterate through the array again to check if the array is ordered.
Attaching my C++ solution and the three test cases
1. [1 2 3 4 5 6] - Already sorted no swaps necessary
2. [1 2 3 9 6 7 4 12 13] - One swap of 9 and 4 makes the array sorted
3. [1 2 6 3 4 5] - A single swap cannot make the array sorted.
4. [1 2 9 9 2] - A single swap of 9 and 2 makes the array sorted
// http://www.careercup.com/question?id=5738109364862976
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector <int> elements;
int tmp_element;
// Store the array elements in a vector for easier access
unsigned int num_elements;
cin >> num_elements;
for(unsigned int i=0; i<num_elements; ++i)
{
cin >> tmp_element;
elements.push_back(tmp_element);
}
int min_element, min_element_index, i, swap_index = 0;
bool ordered = true;
for(i=0; i<elements.size()-1; ++i)
{
if(elements[i] >= elements[i+1])
{
swap_index = i;
break;
}
}
// If there are more elements to be handled by the loop
if(i < elements.size()-1)
{
min_element = elements[i+1];
min_element_index = i+1;
if(elements.size() > i+1)
{
for(unsigned int j=i+2; j<elements.size(); ++j)
{
if(elements[j] < min_element)
{
min_element = elements[j];
min_element_index = j;
}
}
}
// Swap the elements
tmp_element = elements[swap_index];
elements[swap_index] = elements[min_element_index];
elements[min_element_index] = tmp_element;
}
else
{
// All the elements are already handled by the previous for loop
// Not even a single swap is needed in this case
ordered = true;
}
if(ordered)
{
for(unsigned int i=0; i<elements.size()-1; ++i)
{
if(elements[i] > elements[i+1])
{
ordered = false;
break;
}
}
}
if(ordered)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
I see a lot of Java Code to tackle this problem. My solution makes use of Python
from collections import defaultdict
my_list = [5,3,4,6,7,5,3,2,1]
occurrence_count = defaultdict(int)
for item in my_list:
occurrence_count[item] += 1
duplicate_count = {dup: occurrence_count[dup] for dup in occurrence_count if occurrence_count[dup] > 1}
print len(duplicate_count)
print duplicate_count.keys()
After hours of head scratching was still not able to understand the min logic that is used in the most accepted answer. But came up with my own in Python that is quite straightforward to understand.
- RGK June 14, 2015