FastPrep
Problem · Greedy

King-Dreams-I (Intuit India)

Learn this problem
● HardIntuit logoIntuitINTERNOA

Problem statement

Once upon a time, a King saw a dream, where if his kingdom has good line of tanks, meaning tanks lined up side by side in a certain way, they will become invincible.

Now, since you are the advisor of the king, he has asked you to create a good line of tanks.

There are m types of tanks, numbered 1 through m, and we have infinite amount of tanks for each type.

Come up with a good line of size n tanks. If there are multiple good lines return one which is lexicographically smallest.

A good line is a configuration where tanks lined up in an array and the count of subarrays with only distinct tank types is maximum. e.g {3, 4, 4, 5} contains 6 subarrays with distinct tanks: {3}, {4}, {4}, {5}, {3, 4}, {4, 5}

An array x is lexicographically smaller than an array y if there exists an index i such that xi < yj for all 1 <= j < i. Less formally, at the first index i in which they differ, x[i] < y[i].

Constraints

1 <= n <= 100000
1 <= m <= 10000000

Function

createGoodLineOfTanks(n: int, m: int) → int[]

Examples

Example 1

n = 1m = 2return = [1]

Max subarrays count with distinct tanks for line size 1 is 1. Possible lines - {1}, {2} We choose {1} as it is lexicographically smallest.

Example 2

n = 2m = 1return = [1, 1]

The only possible line - {1, 1}

Example 3

n = 2m = 2return = [1, 2]

Possible lines: {1, 1}, {1, 2}, {2, 1}, {2, 2} Lines {1, 2} and {2, 1} have max count of subarrays with distinct tanks.

Constraints

1 <= n <= 100000
1 <= m <= 10000000

More Intuit problems

drafts saved locally
public int[] createGoodLineOfTanks(int n, int m) {
    // write your code here
}
n1
m2
expected[1]
checking account