Can anyone help in finding o(n) or o(n log n) solution for this particular problem.
Thanks in advance
Our Chef is opening a new restaurant in the city. Today being the inauguration night of his new restaurant
and Chef’s huge popularity has attracted a large crowd for the grand opening. For convenience
of the customers, cars of all the customers have been marked with a number from 0 to N-1 where N is the
total number of cars, corresponding to their parking space number in which each car has to be parked.
Due to the large crowd, the car parking is full except for one parking space. Moreover, as the cars came too frequently, they could not be parked in their respective parking space. Poor valet at the restaurant’s parking, Raka, is left with the arduous task of parking the cars at their respective places.
Luckily for him, parking has been closed and no more cars are coming and he can now arrange the cars in
their proper places. As Raka is left alone to park the cars, he can only move one car from one parking to the
other parking. He can use the empty parking space to move the cars aroung. He wants to arrange the cars in
as few moves as possible. Raka asks you for help in finding the optimal strategy to arrange cars in their proper
/* this is just an attempt */ #include <stdio.h> #define SIZE 10
int a[SIZE+1] = {0};
int count;
int idx;
int resolve_location(int from, int to, int free)
{
a[free] = a[to];
a[to] = a[from];
count += 2;
My attempt.
This is O(n) solution. The logic is if the free index is less than n, in that case we will move the original index value and this will be counted as 1 move. If free is n(last one) in that case we will move the current index value to that, thus freeing up the current index and the process continues till the array is sorted.
My solution: find loops. sum of (number of cars in a loop + 1)
def arrangeCars(numList):
nlList = [[num, 0] for num in numList]
moves = 0
for i in xrange(len(numList)):
l, nlList = findloop(nlList, i)
moves += l
return moves
def findloop(nlList, i):
if nlList[i][1] == 1:
return (0, nlList)
if nlList[i][0] == i:
nlList[i][1] = 1
return (0, nlList)
i = nlList[i][0]
num = 1
while nlList[i][1] != 1:
nlList[i][1] = 1
i = nlList[i][0]
num += 1
return (num, nlList)
According to me, pairs where car i has taken j’s position and car j has taken i’s position will take 3 steps to rearrange. after performing all such pair rearrangements we will be left with completely unarranged cars, each will take one step and one extra step. so the solution is 3*number of pairs + unarranged cars + 1.
#include <iostream>
using namespace std;
int main()
{
int test_cases;
int num_of_cars;
int arr[1000];
cin >> test_cases;
int c = 0;
int extra = 0;
while(test_cases--) {
c = 0;
extra = 0;
cin >> num_of_cars;
for(int i = 0; i < num_of_cars; i++) {
cin >> arr[i];
}
for(int i = 0; i < num_of_cars; i++) {
if(arr[i] == i) continue;
if(i == arr[arr[i]]) {
arr[arr[i]] = arr[i];
arr[i] == i;
c += 3;
} else {
c += 1;
extra = 1;
}
}
cout << c + extra << endl;
}
}
public static void main(String[] args) {
int n,t;
Scanner sc = new Scanner(System.in);
t=sc.nextInt();
while(t-- > 0)
{
int count;
System.out.println("enter no of cars");
n=sc.nextInt();
count=n;
parking = new int[n];
carInplace = new int[n];
for(int i=0;i<n;i++)
{
System.out.println("enter the car number");
parking[i]=sc.nextInt();
if(i==parking[i]) //checks for cars in place
carInplace[i]=1;
}
for(int i=0;i<n;i++)
{
if(carInplace[i]==0)
count=count+loop(i);
}
System.out.println(count);
}
}
//counts how many loops are there
public static int loop(int start)
{
int i=start;
carInplace[i]=1;
while(parking[i]!=start)
{
i=parking[i];
carInplace[i]=1;
}
return 1;
}
static int carInplace[],parking[];
public static void main(String[] args) {
int n,t;
Scanner sc = new Scanner(System.in);
t=sc.nextInt();
while(t-- > 0)
{
int count;
System.out.println("enter no of cars");
n=sc.nextInt();
count=n;
parking = new int[n];
carInplace = new int[n];
for(int i=0;i<n;i++)
{
System.out.println("enter the car number");
parking[i]=sc.nextInt();
if(i==parking[i]) //checks for cars in place
carInplace[i]=1;
}
for(int i=0;i<n;i++)
{
if(carInplace[i]==0)
count=count+loop(i);
}
System.out.println(count);
}
}
//counts how many loops are there
public static int loop(int start)
{
int i=start;
carInplace[i]=1;
while(parking[i]!=start)
{
i=parking[i];
carInplace[i]=1;
}
return 1;
}
The questions is incomplete without us knowing where does the Free space exist ?
Within the range of 1-n ? or outside.
The outputs for both cases will be different and since we do not know which case to code this is a incomplete questions.
Or am I missing something here ?
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
ll test, n, i, j;
cin >> test;
while (test--)
{
cin >> n;
ll arr[n + 5];
for (i = 0; i < n; i++)
cin >> arr[i];
i = 0;
ll sum = 0;
while (i < n)
{
j = i;
while (j < n and j == arr[j])
j++;
if (j == n)
break;
sum += 1;
while (j != arr[j])
{
ll k = arr[arr[j]];
arr[arr[j]] = arr[j];
arr[j] = k;
sum += 1;
}
sum++;
i++;
}
cout << sum << endl;
}
return 0;
}
