- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Given a permutation of N elements from 0 to N-1. A fixed point is an index at which the value is same as the index i.e. arr[i] = i. You are allowed to make at most 1 swap. Find the maximum number of fixed points that you can get.

If input array is {0, 1, 2, 3, 4, 6, 5} then answer is 7.

- To adjust fixed point, we have to swap 6 and 5
- After this entire array becomes fixed point and maximum value of fixed point is 7.

- Create an array pos which keeps the position of each element in the input array
- Now, we traverse the array and have the following cases −
- If, a[i] = i. We can simply increment the count and move on
- If, pos[i] = a[i] which means that swapping the 2 terms would make i and a[i] fixed points, hence increasing the count by 2. Keep in mind that swap can be done at most once.

- At the end of the traversal, if we haven’t made any swap, it means that our swap was not able to increase count by 2, so now if there are at least 2 elements which are not fixed points, we can make a swap to increase count by 1, i.e. make one of those points a fixed point.

#include <bits/stdc++.h> using namespace std; int getMaximumFixedPoints(int arr[], int n) { int i, pos[n], count = 0, swapped = 0; for (i = 0; i < n; i++) pos[arr[i]] = i; for (i = 0; i < n; i++) { if (arr[i] == i) { count++; } else if (swapped == 0 && pos[i] == arr[i]) { count += 2; swapped = 1; } } if (swapped == 0 && count < n - 1) { count++; } return count; } int main() { int arr[] = {0, 1, 2, 3, 4, 6, 5}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl; return 0; }

When you compile and execute above program. It generates following output −

Maximum edges = 7

- Related Questions & Answers
- Find Maximum number possible by doing at-most K swaps in C++
- Largest permutation after at most k swaps in C++
- Program to find number of sequences after adjacent k swaps and at most k swaps in Python
- Finding the maximum number using at most one swap in JavaScript
- Maximum sum subarray removing at most one element in C++
- Maximum average of a subarray of size of at least X and at most Y in C++
- Maximum Subarray Sum after inverting at most two elements in C++
- Number of Integral Points between Two Points in C++
- Maximum number of segments that can contain the given points in C++
- Maximum subarray sum by flipping signs of at most K array elements in C++
- Maximum points of intersection n circles in C++
- Maximum points of intersection n lines in C++
- Find the maximum cost of an array of pairs choosing at most K pairs in C++
- Maximize the maximum subarray sum after removing at most one element in C++
- Find number of endless points in C++

Advertisements