Question

In: Computer Science

In this program, the user will enter some permutation of the integers 0 to n-1, inclusive,...

In this program, the user will enter some permutation of the integers 0 to n-1, inclusive, (each integer in that range will appear exactly once) followed by -1 to indicate the end of the input. The user will never input more than 100 numbers. Your job is to store all the numbers in an array in the order they are input. For example if the user inputs 3 0 2 1 -1 then you should store the 3 at index 0 in an array, 0 at index 1, 2 and index 2, and 1 at index 3. Once you have stored the data in your array your task is to find the maximum length cycle in the array. To answer the question, "What does cycle mean?", interpret the value at index i as the next index in the array that we should visit. So in the example above, at index 0 is the value 3. This indicates that we should go visit index 3 of the array next. Once we go to index 3 we find the value 1. This tells us to go visit index 1 next. Once we go to index 1 we find the value 0. This tell us to go visit index 0 next. But we've already visited index 0 (it's where we started). If and when you get back to your starting location (i.e. we started at location 0 and then got back to that location because the value at index 1 told us to go to 0) we stop and define those indices to be a cycle. So in this case the cycle is created from index 0 3 1 (and then back to 0). This cycle has a length of 3 since it tooks us 3 steps to get back to the starting location. Your job is to detect the longest (max number of steps to get back to the starting point) cycle in the array. Notice, once we start at 0 and find a cycle of length 3, we could then repeat the process starting at index 1. As we start at index 1 we would visit 0, from 0 we would go to 3, and from 3 back to 1. The same cycle is detected and thus its length is the same. We have not found anything longer. From there we could look for a cycle starting at location 2. At index 2 we find the value 2 which tells us to simply stay put (or go back to itself). Thus, we have a cycle of length 1 since 2 only requires one step before we get back to the starting point. By doing this cycle-walking process starting at each point in the array we can determine the longest cycle.

Note: You may realize there is some inefficiency in what we've described. We would find the cycle of 0 3 1 three times as we start our search from 0, then from 1, and finally from 3. You can potentially use another array to avoid this duplicated work, but you are not required to do so. It is fine to use an "inefficient" approach to solve this problem.

Your program should only output a single number on the last line of output which should be the length of the longest cycle present in the array.

Example 1

If the user entered:

3 0 2 1 -1

Your program should output exactly the lines:

3

Example 2

If the user entered:

1 2 3 4 0 -1

Your program should output exactly the lines:

5

Example 3

If the user entered:

0 1 2 3 4 -1

Your program should output exactly the lines:

1

Example 3

If the user entered:

1 0 3 4 2 -1

Your program should output exactly the lines:

3

I really need help and the language is C++

Solutions

Expert Solution

To solve this question we need to use a depth-first search (DFS) function that will visit each array and check if it is visited or not. The get_longest_cycle() method returns the maximum length of the cycle by checking each cycle and updating the value of the max. The main() function is used to take input from user till it enters -1 and to print out the final max_length.

The necessary comments that will help you understand the solution.

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
// DFS method
void dfs(int start, int idx, int a[], int N, bool *visited, int &len)
{
    if (idx >= N)
    {
        len = 1;
        return;
    }
    visited[idx] = true;
    len++;
    if (visited[a[idx]] == false)
    {
        dfs(start, a[idx], a, N, visited, len);
    }
    else if (start == idx)
        return;
}

// Function to get the maximum length of the cycle
int get_longest_cycle(int a[], int N)
{
    int maxlen = -1;
    bool *visited = new bool[N];
    for (int i = 0; i < N; i++)
        visited[i] = false;
    for (int i = 0; i < N; i++)
    {
        if (visited[i] == false)
        {
            int len = 0;
            dfs(i, a[i], a, N, visited, len);
            maxlen = max(maxlen, len);
        }
    }
    return maxlen;
}
// Driver Function
int main()
{
    vector<int> v1;
    cout << "Start Entering the numbers in array(Enter -1 to stop)" << endl;
    for (int i = 0; i < 100; i++)
    {
        int input;
        cin >> input;
        if (input != -1)
        {
            //-1 condition check
            v1.push_back(input);
        }
        else
        {
            break;
        }
    }
    int size = v1.size();
    int a[size];
    for (int i = 0; i < size; i++)
    {
        a[i] = v1[i];
    }
    // Output of the max:length;
    cout << get_longest_cycle(a, size);
    return 0;
}

I hope you have understood the solution. If you like the solution kindly upvote it.


Related Solutions

Question Write a C program that asks the user to enter two integers x and n....
Question Write a C program that asks the user to enter two integers x and n. Then the program computes xn (=x * x * x …… (n times)) using for loop. and give me an output please use printf and scanf #include int main(void) {     //Declare required variables             //read two integers x , n from the keyboard                 //compute xn using for loop                     printf("< Your name >\n");...
C Program 1. Write a program that prompts the user to enter 3 integers between 1...
C Program 1. Write a program that prompts the user to enter 3 integers between 1 and 100 from the keyboard in function main and then calls a function to find the average of the three numbers. The function should return the average as a floating point number. Print the average from main.The function header line will look something like this:float average(int n1, int n2, int n3) STOP! Get this part working before going to part 2. 2. Create a...
The program will prompt the user to enter a number between [10 .. 20] (inclusive). After...
The program will prompt the user to enter a number between [10 .. 20] (inclusive). After verifying that the number is within the proper range, you will generate that many random numbers and place them into a dynamically allocated array. Your program will then display the contents of the array (with 4 numbers per line). Next, you will sort the values in descending order (from largest to smallest). Lastly, you will display the sorted numbers (again, with 4 per line)....
JAVA Language: Write a program that prompts the user to enter a positive integer n (0...
JAVA Language: Write a program that prompts the user to enter a positive integer n (0 up to 232 -1). You must write a function that takes as input n and returns a string s representing the number n in binary. For this assignment, you must use the method of successive division by 2 to convert the number to binary. Your main program must print out s. Example: If the user enters the number 66, your program must print out...
Java Program 1. Write a program that asks the user: “Please enter a number (0 to...
Java Program 1. Write a program that asks the user: “Please enter a number (0 to exit)”. Your program shall accept integers from the user (positive or negative), however, if the user enters 0 then your program shall terminate immediately. After the loop is terminated, return the total sum of all the previous numbers the user entered. a. What is considered to be the body of the loop? b. What is considered the control variable? c. What is considered to...
Write a program that prompts user to enter integers one at a time and then calculates...
Write a program that prompts user to enter integers one at a time and then calculates and displays the average of numbers entered. Use a while loop and tell user that they can enter a non-zero number to continue or zero to terminate the loop. (Switch statement) Write a program that prompts user to enter two numbers x and y, and then prompts a short menu with following 4 arithmetic operations: Chose 1 for addition Chose 2 for subtraction Chose...
A. Write a program 1. Prompt the user to enter a positive integer n and read...
A. Write a program 1. Prompt the user to enter a positive integer n and read in the input. 2. Print out n of Z shape of size n X n side by side which made up of *. B. Write a C++ program that 1. Prompt user to enter an odd integer and read in the value to n. 2. Terminate the program if n is not odd. 3. Print out a cross shape of size n X n...
Write a mips assembly language program to ask the user to enter two integers A and...
Write a mips assembly language program to ask the user to enter two integers A and B and then display the result of computing the expression: A + 2B - 5.
The program asks user to enter three integers, and the displays a message indicating whether the...
The program asks user to enter three integers, and the displays a message indicating whether the numbers are in sequential order, in reverse order or in neither order. Find the errors and correct the program codes in the if comparison expressions. (10 points) 1.     using System; 2.     using static System.Console; 3. 4.     class Sorting 5.     { 6.              static void Main() 7.              { 8.                       int num1, num2, num3; 9.                       string snum1, snum2, snum3; 10.                    Write ("Enter first number "); 11.                    snum1...
C++ Write a program that prompts the user to enter 50 integers and stores them in...
C++ Write a program that prompts the user to enter 50 integers and stores them in an array. The program then determines and outputs which numbers in the array are sum of two other array elements. If an array element is the sum of two other array elements, then for this array element, the program should output all such pairs separated by a ';'. An example of the program is shown below: list[0] = 15 is the sum of: ----------------------...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT