Just an hint: Sieve of Eratosthenes - Wikipedia[^]

How many divisions/modulos do you need to fill a sieve of Eratosthenes ?

Can you find a way to avoid divisions/modulos ?

15,500,453 members

This problem is the extreme version of Fizz Buzz. You are given a list of K distinct integers A and a list of K characters S. Both lists are numbered from 1 to K. The integer Ai corresponds to the character Si.

Denote B as the subset of A. There will be a rule for each possible subset: if an integer x is only divisible by all elements in B, print a string which is the concatenation of the corresponding character of each element in B, sorted by the index in ascending order. However, if B is an empty subset, print the first digit of x instead.

Does it look complicated? Do not worry, as it is just a generalization of the regular Fizz Buzz. For example, if A = [3, 5] and S = [F, B], you will get the normal Fizz Buzz problem. You can also check the Sample Test Cases for further understanding.

**Your task is simple. Given the array A and S, with all rules from the subset of A, print the Extreme Fizz Buzz from 1 to N.**

**Format Input**

The first line consists of 2 integers N and K.

The second line consists of a string S which has exactly K lower-case latin alphabet

characters.

The third line consists of K integers A1, A2, . . . , AK.

**Format Output**

Output N lines. The i-th line is the Extreme Fizz Buzz of i, where i is integer from 1 to N.

**Constraints**

• 1 ≤ N, K ≤ 100000

• 1 ≤ Ai ≤ 100000

• It is guaranteed that the integers in A are distinct

• It is guaranteed that the characters in S are upper-case latin alphabet characters

**Sample Input & Output 1 (Standard Input And Output)**

15 2

FB

3 5

1

2

F

4

B

F

7

8

F

B

1

F

3

4

FB

**Sample Input & Output 2 (Standard Input And Output)**

15 2

BF

3 5

1

2

B

4

F

B

7

8

B

F

1

B

3

4

BF

**Sample Input & Output 3 (Standard Input And Output)**

13 3

JLB

2 4 3

1

J

B

JL

5

JB

7

JL

B

J

11

JLB

13

**What I have tried:**

Denote B as the subset of A. There will be a rule for each possible subset: if an integer x is only divisible by all elements in B, print a string which is the concatenation of the corresponding character of each element in B, sorted by the index in ascending order. However, if B is an empty subset, print the first digit of x instead.

Does it look complicated? Do not worry, as it is just a generalization of the regular Fizz Buzz. For example, if A = [3, 5] and S = [F, B], you will get the normal Fizz Buzz problem. You can also check the Sample Test Cases for further understanding.

The first line consists of 2 integers N and K.

The second line consists of a string S which has exactly K lower-case latin alphabet

characters.

The third line consists of K integers A1, A2, . . . , AK.

Output N lines. The i-th line is the Extreme Fizz Buzz of i, where i is integer from 1 to N.

• 1 ≤ N, K ≤ 100000

• 1 ≤ Ai ≤ 100000

• It is guaranteed that the integers in A are distinct

• It is guaranteed that the characters in S are upper-case latin alphabet characters

15 2

FB

3 5

1

2

F

4

B

F

7

8

F

B

1

F

3

4

FB

15 2

BF

3 5

1

2

B

4

F

B

7

8

B

F

1

B

3

4

BF

13 3

JLB

2 4 3

1

J

B

JL

5

JB

7

JL

B

J

11

JLB

13

#include <stdio.h> int main() { int N, K, A[100005], i, a, j, fl; scanf("%d %d", &N, &K); getchar(); char S[K + 5]; scanf("%s", S); getchar(); for(i = 0; i < K; i++) { scanf("%d", &A[i]); } getchar(); for(i = 1; i <= N; i++) { a = i; fl = 0; for(j = 0; j < K; j++) { if(a % A[j] == 0) { printf("%c", S[j]); fl = 1; } } if(fl == 1) { printf("\n"); } else { if(a >= 10) { a %= 10; } printf("%d\n", a); } } return 0; }

Comments

Richard MacCutchan
29-Jan-21 7:54am

Stay away from Fizz Buzz and similar sites.

Dave Kreskowiak
29-Jan-21 13:09pm

I'll give you a hint on these "time-bound" tests. If your algorithm uses a loop inside a loop, you've already failed. You have to solve the problem from an entirely different approach.

Dummy Coursera
30-Jan-21 0:06am

Ok, thank you very much

Just an hint: Sieve of Eratosthenes - Wikipedia[^]

How many divisions/modulos do you need to fill a sieve of Eratosthenes ?

Can you find a way to avoid divisions/modulos ?

How many divisions/modulos do you need to fill a sieve of Eratosthenes ?

Can you find a way to avoid divisions/modulos ?

Permalink

Share this answer

v2

Comments

Dummy Coursera
30-Jan-21 0:06am

Thank You Very Much

We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!

Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!

Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]

Permalink

Share this answer

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900