• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

CodeChef Code SGARDEN

August 4, 2014 by Dhaval Dave

This time Sheriff gathered all the bandits in his garden and ordered them to line up. After the whistle all bandits should change the order in which they stand.
Sheriff gave all the bandits numbers from 1 to N. For each place i he determined the unique position j. After whistling the bandit staying on position i should run to the j-th position. Sheriff loved seeing how the bandits move around, and he continued whistling until the evening. He finished the game only when he noticed that the bandits are in the same order in which they were standing originally.
Now the Sheriff asks the question: How many times has he whistled?

Input:

  • The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains a single integer N denoting the number of bandits. The second line contains N space-separated integers A1, A2, …, AN denoting that the bandit staying on position i should run to the Ai-th position after the whistle.

2
3
1 2 3
5
2 3 1 5 4

Output:

1
6

Logic :

Method 1) You can create a function where you pass initial arrangement ie 2 3 1 5 4.
in loop you can create result array first as 1 2 3 4 5 and generate new arrangement array ie 3 1 2 5 4 and check whether its matching  with  resultant array 1 2 3 4 5 or not , again with same indexing create next arrangement ie 2 3 1 4 5 and check … and so on, Keep one counter when both matches return count.

Method 2) You can optimize space with just using one array Initial and search whether all are in increasing order ( 1,2,3,4,5) then return count.

Method 3) For which I have code :
Pass array of initial arrangement ie 2 3 1 5 4  and Integers ( 1 to 5 ) to a function sgarden. Then calculate that each integer is getting its own value After how many iteration of rearrangement.
Such way calculate for each integer (1 to 5) and find lcm of this count which will be total number of rearrangement needed.
example : 1,2,3 are getting its own place after 3 iteration. While 4 and 5 after 2.
So whole array will get rearranged after 6 iterations.Full coverage of rearrangements 
the bandits positions are:
0. 1 2 3 4 5
1. 3 1 2 5 4
2. 2 3 1 4 5
3. 1 2 3 5 4
4. 3 1 2 4 5
5. 2 3 1 5 4
6. 1 2 3 4 5.

PS : for understanding and for loop’s indexing purpose we have decremented initial array 2 3 1 5 4 by 1. and hence passing 1 2 0 4 3.

Thanks to Dhaval for suggesting this approach and Article

Code

#include <stdio.h>
 
int sgarden(int n,int a[]){
    int i=1;
    int ops=a[n]; 
    while(ops!=n){
        ops=a[ops];
        i++;
    }//while
return i;
}
int lcm ( int a, int b ){
    int x=a;
    int y=b;
    int c; 
    while ( a != 0 ) { 
        c = a; a = b%a;  b = c;
        } 
    return (x*y)/b;     



}
int main()
{
int i,maxp=1;//as maxlp is needed in getting lcm, store 1.
int a[]={2,3,1,5,4};
    for(i=0;i<(sizeof(a)/sizeof(int));i++){a[i]–;} //decreeing 1 from each

    for(i=0;i<(sizeof(a)/sizeof(int));i++){
    int count = sgarden(i,a);//storing rearrangement count for each index 1 to 5.
    maxp=lcm(count,maxp); // storing lcm of each.
    }//for
printf(“Max permutations %d”,maxp);
return 0;
}

You can see Working code at  : http://ideone.com/qXGU6w

Similar Articles

Filed Under: Flipkart Interview Questions, Microsoft Interview Questions Tagged With: Array, codechef

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Longest Increasing Subsequence

flattens 2 D linked list to a single sorted link list

SAP Interview Questions

Print vertical sum of all the axis in the given binary tree

Printing Longest Common Subsequence

Maximum occurred Smallest integer in n ranges

SAP Off Campus Hiring_ March 2015 Verbal Skills

Find min element in Sorted Rotated Array (Without Duplicates)

CodeChef’ RRCOPY

Print Power Set of a Set

C++ OOPs Part1

Find Percentage of Words matching in Two Strings

The greedy coins game Dynamic Programming

Leetcode: Edit Distance

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Find Pythagorean Triplets in an array in O(N)

Diagonal Traversal of Binary Tree

FizzBuzz Solution C C++

Python Array String

Minimum insertions to form a palindrome

Memory Efficient LinkedList

Max Sum in circularly situated Values

strtok()

Fibonacci Hashing & Fastest Hashtable

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Number of Islands BFS/DFS

The Magic HackerEarth Nirvana solutions Hiring Challenge

Copyright © 2025 · Genesis Framework · WordPress · Log in