Question Set 4

 

This is question set 4. Another day another set.This set contains 3 questions from the famous CSES problems set.This set has some problems that new programmers must give a try. Happy Coding!

"while(!success) keep trying”

 Problem 1- Repetitions (Easy)

You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character. The only input line contains a string of n characters. Print one integer: the length of the longest repetition.

Constraints

• 1 ≤ n≤ 10^6

Example
Input: ATTCGGGA
Output: 3

Link to the question- https://cses.fi/problemset/task/1069

 

Problem 2-Weird Algorithm (Easy)

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:

3→10→5→16→8→4→2→13→10→5→16→8→4→2→1

Your task is to simulate the execution of the algorithm for a given value of n.The only input line contains an integer n.
Print a line that contains all values of n during the algorithm.

Constraints

• 1≤n≤10^6

Example

Input:3

Output:3 10 5 16 8 4 2 1

Link to the question-https://cses.fi/problemset/task/1068

 

Problem 3-Missing Number(Easy)

You are given all numbers between 1,2,…,nexcept one. Your task is to find the missing number.
Print the missing number.

Constraints

• 2≤n≤2⋅105

Example

Input:n=5 arr=[2 3 1 5]

Output:4

Link to the question-https://cses.fi/problemset/task/1083

 

Problem 4-Hard Sequence (Easy)

Chef decided to write an infinite sequence. Initially, he wrote 0, and then he started repeating the following process:

• Look at the last element written so far (the l-th element if the sequence has length l so far); let's denote it by x.
• If x does not occur anywhere earlier in the sequence, the next element in the sequence is 0.
• Otherwise, look at the previous occurrence of x in the sequence, i.e. the k-th element, where k<l this element is equal to x and all elements between the k+1 and $l-1$-th are different from x$x$. The next element is l−k, i.e. the distance between the last two occurrences of x.

The resulting sequence is $(0,0,1,0,2,0,2,2,1,\dots )$: the second element is 
$0$ since 
$0$ occurs only once in the sequence $(0)$, the third element is $1$ since the distance between the two occurrences of 
$0$ in the sequence $(0,0)$ is $1$, the fourth element is $0$ since $1$ occurs only once in the sequence $(0,0,1)$, and so on.

Chef has given you a task to perform. Consider the N-th element of the sequence (denoted by x$x$) and the first N elements of the sequence. Find the number of occurrences of x$x$ among these N elements.

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains a single integer N
  
• For each test case, print a single line containing one integer the number of occurrences of the Nth element Nthe

Constraints

• 1≤T≤128
• 1≤N≤128

Link to the question-https://www.codechef.com/problems/HRDSEQ