Directi Coding Round Question

Can anyone help in finding o(n) or o(n log n) solution for this particular problem.

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

places.

Sample Input File:

2

3

1 0 2

4

2 1 3 0

Output:

3

4

/* 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;

``````    if(a[free] == from)
{
a[from] = from;
++count;
return free;
}

return from;
}
int main()
{
int NTest, i, j, NCars;

scanf( "%d", &NTest );

while(NTest--)
{
scanf( "%d", &NCars );
count = 0;

for(i = 0;i < NCars; ++i)
scanf( "%d", &a[i] );

idx = NCars;
a[NCars] = NCars;

for(i = 0;i <= NCars; ++i)
{
if(a[i] == i)
continue;

idx = resolve_location(i, a[i], idx);
}
printf( "%d\n", count );
}

return 0;
``````

}

1 Like

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.

Following is my code:

`````` #include <iostream>
#include <cmath>
#include <cstring>
#include<cstdio>
#include<vector>
#define For(i,n) for(int i=0;(i)<n;i++)
#define mp make_pair
#define pb push_back
using namespace std;

int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n+1],indx[n],sorted=0;
For(i,n){
cin>>arr[i];
indx[arr[i]]=i;
if(arr[i]!=i)sorted++;
}
int free=n;
int i=0,cnt=0,y;
while(1){
//cin>>y;
//For(i,n+1)cout<<arr[i]<<" ";cout<<endl;For(i,n)cout<<indx[i]<<" ";cout<<endl;cout<<sorted;cout<<endl;cout<<endl;
if(sorted<=0)break;
if(free<n && arr[free]!=free ){
arr[free]=arr[indx[free]];
int x=indx[free];
indx[free]=free;
free=x;
arr[free]=-1;
sorted--;
cnt++;
//indx[free]=
}
else if(free==n && sorted!=0 && arr[i]!=i){
arr[free]=arr[i];
indx[arr[i]]=free;
arr[i]=-1;
free=i;
i++;
//  sorted++;
cnt++;
}
else if(arr[i]==i){
i++;
}
}
cout<<cnt<<endl;
}
}``````

The code here is in Java. I believe it works correctly. If it fails any test cases, kindly let me know.

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{

Scanner scan = new Scanner(System.in);
int T = scan.nextInt();

for(int x = 0; x < T; x++)
{
int size = scan.nextInt();
int[] arr = new int[size + 1];
int free = size;
int count = 0;

for(int i = 0; i < size; i++)
arr[i] = scan.nextInt();
arr[free] = size;

for(int i = 0; i <= size; i++)
{
if(arr[i] == i)
continue;
else
{
if(arr[i] != free)
{
arr[free] = arr[arr[i]];
//				System.out.println(arr[i] + " -> " + free + ": " + arr[arr[i]]);
arr[arr[i]] = arr[i];
//				System.out.println(i + " -> " + arr[i] + ": " + arr[i]);
count += 2;
}
else
{
arr[arr[i]] = arr[i];
//				System.out.println(i + " -> " + arr[i] + ": " + arr[i]);
count++;
}

if(arr[free] == i)
{
arr[i] = arr[free];
//				System.out.println(i + " -> " + arr[i] + ": " + arr[i]);
count++;
}
else
free = i;
//arr[free] = -1;

}
}

System.out.println(count);

//	for(int i = 0; i <= size; i++)
//		System.out.print(arr[i] + "  ");
//	System.out.println("\n");
}
}
}``````

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)``````
1 Like

1 Like

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;
}
}``````

import java.util.*;

class parkingLot
{

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;
}
``````

}

import java.util.*;

class parkingLot{

``````    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 ?