K Distinct Array CodeChef Solution

Problem -K Distinct Array CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

K Distinct Array CodeChef Solution in C++17

#include <bits/stdc++.h>
using namespace std;


int main() {
	// your code goes here
	int t; cin>>t;
	while(t--){
	    long long int n,k;
	    cin>>n>>k;
	    
	    if(k==n){
	        for(int i=0; i<n; i++){
	           cout<<"1"<<" ";
	        }
	        cout<<endl;
	    }else if(n*(n+1)/2==k){
	        for(int i=0; i<n; i++){
	            cout<<i+1<<" ";
	        }
	        cout<<endl;
	    }else {
	        k=k-n;
	       long long  int x=0;
	        while(x<=k){
	            cout<<x+1<<" ";
	          
	            k-=x;
	            x++;
	        }
	      
	       
	       long long int  j=x;
	       while(j<n){
	           cout<<x-k<<" ";
	           j++;
	       }
	       cout<<endl;
	    }
	   
	}
	return 0;
}

K Distinct Array CodeChef Solution in C++14

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

int main() {
	// your code goes here
	ll t,m,n,i,j,k,p,q;
	cin>>t;
	while(t--)
	{
	    cin>>n>>k;
	    ll a[n];
	    for(i=0;i<n;i++)
	    {
	        a[i]=i+1;
	    }
	    p=(n*(n+1))/2;
	    if(k==p)
	    {
	        for(i=0;i<n;i++)
	        {
	            cout<<a[i]<<" ";
	        }
	        cout<<endl;
	    }
	    else
	    {
           p--;
           a[n-1]=1;
           for(i=n-2;i>=0;i--)
           {
               if(p-(i+1)>=k)
               {
                   p-=(i+1);
                   a[i]=1;
               }
               else
               break;
           }
           if(i>=0)
           {
           j=a[i];
           k=p-k;
           if(k>0)
           {
           k=j-k;
           a[0]=k+1;
           }
           }
           for(i=0;i<n;i++)
           cout<<a[i]<<" ";
           cout<<endl;
	    }
	}
	return 0;
}

K Distinct Array CodeChef Solution in PYTH 3

# cook your dish here
for _ in range(int(input())):
    N,K = [int(x) for x in input().split()]
    good = N
    A = [1]
    while (good < K):
        good += len(A)
        A.append(A[-1]+1)
    extra = good - K
    if (extra > 0):
        A[-1] -= A[-1-extra]
    while (len(A) < N):
        A.append(A[-1])
    print(*A)

K Distinct Array CodeChef Solution in C

#include <stdio.h>

int main(void) {
	// your code goes here
	int T;
	scanf("%d", &T);
	while(T--)
	{
	    long N,K;
	    scanf("%ld%ld", &N,&K);
        K = K - N;
        long val = 0;
        int group = 0;
        while(K >= val)
        {
            group++;
            val += group;
        }
        
        //    _ _ _ _ _
	    //5// ...... |1 + 2 + 3 + 4 <= tot(1) < 1 + 2 + 3 + 4 + 5 
	    //4// 1....1 |1 + 2 + 3     <= tot(2) < 1 + 2 + 3 + 4    
	    //3// 11...1 |1 + 2         <= tot(3) < 1 + 2 + 3
	    //2// 111..1 |1             <= tot(4) < 1 + 2
	    //1// 1111.1 |0             <= tot(5) < 1
	    
	    for(int i=0; i<N-group; i++)
	    {
	        printf("1 ");
	    }
	    val -= group;
	    long space = K - val;
	    int diff = 2;
	    for(int i=0; i<space; i++)
	    {
	        printf("%d ",diff);
	        diff++;
	    }
	    printf("1 ");
	    for(int i=0; i<(group-space-1); i++)
	    {
	        printf("%d ",diff);
	        diff++;
	    }
	    printf("\n");
	}
	return 0;
}

K Distinct Array CodeChef Solution in JAVA


import java.util.*;
import java.util.stream.*;
import java.lang.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.io.*;

class Codechef {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static PrintWriter out = new PrintWriter(System.out);
    static DecimalFormat df = new DecimalFormat("0.0000000");
    final static int mod = (int) (1e9 + 7);
    final static int MAX = Integer.MAX_VALUE;
    final static int MIN = Integer.MIN_VALUE;

    // ======================= MAIN ==================================

    public static void main(String[] args) throws IOException {
        int t = readInt();
        // int t = 1;
        preprocess();
        while (t-- > 0) {
            solve();
        }
        out.flush();
    }

    private static void solve() throws IOException {
        int n = readInt();
        long k = readLong();
        long[] dp = new long[n];
        Arrays.fill(dp, 1);
        long sum = n;

        int[] ans = new int[n];
        ans[0] = 1;
        for (int i = 1; i < n; i++) {
            if (i - (k - sum + 1) < 0) {
                ans[i] = ans[i - 1] + 1;
                dp[i] = dp[i - 1] + 1;
                sum += dp[i] - 1;
            } else {
                ans[i] = ans[i - (int) (k - sum + 1)];
                dp[i] = dp[i - 1] - dp[i - (int) (k - sum + 1)] + 1;
                sum += dp[i] - 1;
            }
        }

        printIArray(ans);
    }

    private static void preprocess() throws IOException {

    }

    // ======================= FOR INPUT ==================================
    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(readLine());
        return st.nextToken();
    }

    static long readLong() throws IOException {
        return Long.parseLong(next());
    }

    static int readInt() throws IOException {
        return Integer.parseInt(next());
    }

    static double readDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static char readCharacter() throws IOException {
        return next().charAt(0);
    }

    static String readString() throws IOException {
        return next();
    }

    static String readLine() throws IOException {
        return br.readLine().trim();
    }

    static int[] readIntArray(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = readInt();
        return arr;
    }

    static long[] readLongArray(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
            arr[i] = readLong();
        return arr;
    }

    // ========================= FOR OUTPUT ==================================

    private static void printIList(List<Integer> list) {
        for (int i = 0; i < list.size(); i++)
            out.print(list.get(i) + " ");
        out.println(" ");
    }

    private static void printLList(List<Long> list) {
        for (int i = 0; i < list.size(); i++)
            out.print(list.get(i) + " ");
        out.println(" ");
    }

    private static void printIArray(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            out.print(arr[i] + " ");
        out.println(" ");
    }

    private static void printIArray(int[][] arr) {
        for (int i = 0; i < arr.length; i++)
            printIArray(arr[i]);
    }

    private static void printLArray(long[] arr) {
        for (int i = 0; i < arr.length; i++)
            out.print(arr[i] + " ");
        out.println(" ");
    }

    // ====================== TO CHECK IF STRING IS NUMBER ========================

    private static boolean isInteger(String s) {
        try {
            Integer.parseInt(s);
        } catch (NumberFormatException e) {
            return false;
        } catch (NullPointerException e) {
            return false;
        }
        return true;
    }

    private static boolean isLong(String s) {
        try {
            Long.parseLong(s);
        } catch (NumberFormatException e) {
            return false;
        } catch (NullPointerException e) {
            return false;
        }
        return true;
    }

    // ==================== FASTER SORT ================================

    private static void sort(int[] arr) {
        int n = arr.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++)
            list.add(arr[i]);
        Collections.sort(list);
        for (int i = 0; i < n; i++)
            arr[i] = list.get(i);
    }

    private static void sort(long[] arr) {
        int n = arr.length;
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < n; i++)
            list.add(arr[i]);
        Collections.sort(list);
        for (int i = 0; i < n; i++)
            arr[i] = list.get(i);
    }

    // ==================== MATHEMATICAL FUNCTIONS ===========================

    private static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    private static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    private static int lcm(int a, int b) {
        return (a / gcd(a, b)) * b;
    }

    private static long lcm(long a, long b) {
        return (a / gcd(a, b)) * b;
    }

    private static int mod_power(int a, int b) {
        if (b == 0)
            return 1;
        int temp = mod_power(a, b / 2);
        temp %= mod;
        temp = (int) ((1L * temp * temp) % mod);
        if ((b & 1) == 1)
            temp = (int) ((1L * temp * a) % mod);
        return temp;
    }

    private static int multiply(int a, int b) {
        return (int) ((((1L * a) % mod) * ((1L * b) % mod)) % mod);
    }

    private static boolean isPrime(long n) {
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    // ==================== Primes using Seive =====================

    private static List<Integer> SeivePrime(int n) {
        boolean[] prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        for (int i = 2; i * i <= n; i++) {
            if (prime[i]) {
                for (int j = i * i; j <= n; j += i)
                    prime[j] = false;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= n; i++)
            if (prime[i])
                list.add(i);
        return list;
    }

    // ==================== STRING FUNCTIONS ================================

    private static boolean isPalindrome(String str) {
        int i = 0, j = str.length() - 1;
        while (i < j)
            if (str.charAt(i++) != str.charAt(j--))
                return false;
        return true;
    }

    private static String reverseString(String str) {
        StringBuilder sb = new StringBuilder(str);
        return sb.reverse().toString();
    }

    // ==================== LIS & LNDS ================================

    private static int LIS(int arr[], int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int idx = find(list, arr[i]);
            if (idx < list.size())
                list.set(idx, arr[i]);
            else
                list.add(arr[i]);
        }
        return list.size();
    }

    private static int find(List<Integer> list, int val) {
        int ret = list.size(), i = 0, j = list.size() - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (list.get(mid) >= val) {
                ret = mid;
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return ret;
    }

    private static int LNDS(int[] arr, int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int idx = find2(list, arr[i]);
            if (idx < list.size())
                list.set(idx, arr[i]);
            else
                list.add(arr[i]);
        }
        return list.size();
    }

    private static int find2(List<Integer> list, int val) {
        int ret = list.size(), i = 0, j = list.size() - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (list.get(mid) <= val) {
                i = mid + 1;
            } else {
                ret = mid;
                j = mid - 1;
            }
        }
        return ret;
    }

    // ==================== UNION FIND =====================

    private static int find(int x, int[] parent) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x], parent);
    }

    private static boolean union(int x, int y, int[] parent, int[] rank) {
        int lx = find(x, parent), ly = find(y, parent);
        if (lx == ly)
            return true;
        if (rank[lx] > rank[ly])
            parent[ly] = lx;
        else if (rank[lx] < rank[ly])
            parent[lx] = ly;
        else {
            parent[lx] = ly;
            rank[ly]++;
        }
        return false;
    }

    // ==================== SEGMENT TREE (RANGE SUM) =====================

    public static class SegmentTree {
        int n;
        int[] arr, tree, lazy;

        SegmentTree(int arr[]) {
            this.arr = arr;
            this.n = arr.length;
            this.tree = new int[(n << 2)];
            this.lazy = new int[(n << 2)];
            build(1, 0, n - 1);
        }

        void build(int id, int start, int end) {
            if (start == end)
                tree[id] = arr[start];
            else {
                int mid = (start + end) / 2, left = (id << 1), right = left + 1;
                build(left, start, mid);
                build(right, mid + 1, end);
                tree[id] = tree[left] + tree[right];
            }
        }

        void update(int l, int r, int val) {
            update(1, 0, n - 1, l, r, val);
        }

        void update(int id, int start, int end, int l, int r, int val) {
            distribute(id, start, end);
            if (end < l || r < start)
                return;
            if (start == end)
                tree[id] += val;
            else if (l <= start && end <= r) {
                lazy[id] += val;
                distribute(id, start, end);
            } else {
                int mid = (start + end) / 2, left = (id << 1), right = left + 1;
                update(left, start, mid, l, r, val);
                update(right, mid + 1, end, l, r, val);
                tree[id] = tree[left] + tree[right];
            }
        }

        int query(int l, int r) {
            return query(1, 0, n - 1, l, r);
        }

        int query(int id, int start, int end, int l, int r) {
            if (end < l || r < start)
                return 0;
            distribute(id, start, end);
            if (start == end)
                return tree[id];
            else if (l <= start && end <= r)
                return tree[id];
            else {
                int mid = (start + end) / 2, left = (id << 1), right = left + 1;
                return query(left, start, mid, l, r) + query(right, mid + 1, end, l, r);
            }
        }

        void distribute(int id, int start, int end) {
            if (start == end)
                tree[id] += lazy[id];
            else {
                tree[id] += lazy[id] * (end - start + 1);
                lazy[(id << 1)] += lazy[id];
                lazy[(id << 1) + 1] += lazy[id];
            }
            lazy[id] = 0;
        }
    }

    // ==================== TRIE ================================

    static class Trie {
        class Node {
            Node[] children;
            boolean isEnd;

            Node() {
                children = new Node[26];
            }
        }

        Node root;

        Trie() {
            root = new Node();
        }

        public void insert(String word) {
            Node curr = root;
            for (char ch : word.toCharArray()) {
                if (curr.children[ch - 'a'] == null)
                    curr.children[ch - 'a'] = new Node();
                curr = curr.children[ch - 'a'];
            }
            curr.isEnd = true;
        }

        public boolean find(String word) {
            Node curr = root;
            for (char ch : word.toCharArray()) {
                if (curr.children[ch - 'a'] == null)
                    return false;
                curr = curr.children[ch - 'a'];
            }
            return curr.isEnd;
        }
    }

    // ==================== FENWICK TREE ================================

    static class FT {
        long[] tree;
        int n;

        FT(int[] arr, int n) {
            this.n = n;
            this.tree = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                update(i, arr[i - 1]);
            }
        }

        void update(int idx, int val) {
            while (idx <= n) {
                tree[idx] += val;
                idx += idx & -idx;
            }
        }

        long query(int l, int r) {
            return getSum(r) - getSum(l - 1);
        }

        long getSum(int idx) {
            long ans = 0L;
            while (idx > 0) {
                ans += tree[idx];
                idx -= idx & -idx;
            }
            return ans;
        }
    }

    // ==================== BINARY INDEX TREE ================================

    static class BIT {
        long[][] tree;
        int n, m;

        BIT(int[][] mat, int n, int m) {
            this.n = n;
            this.m = m;
            tree = new long[n + 1][m + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    update(i, j, mat[i - 1][j - 1]);
                }
            }
        }

        void update(int x, int y, int val) {
            while (x <= n) {
                int t = y;
                while (t <= m) {
                    tree[x][t] += val;
                    t += t & -t;
                }
                x += x & -x;
            }
        }

        long query(int x1, int y1, int x2, int y2) {
            return getSum(x2, y2) - getSum(x1 - 1, y2) - getSum(x2, y1 - 1) + getSum(x1 - 1, y1 - 1);
        }

        long getSum(int x, int y) {
            long ans = 0L;
            while (x > 0) {
                int t = y;
                while (t > 0) {
                    ans += tree[x][t];
                    t -= t & -t;
                }
                x -= x & -x;
            }
            return ans;
        }
    }

    // ==================== OTHER CLASSES ================================

    static class Pair implements Comparable<Pair> {
        int first, second;

        Pair(int first, int second) {
            this.first = this.second;
        }

        public int compareTo(Pair o) {
            return this.first - o.first;
        }
    }

    static class DequeNode {
        DequeNode prev, next;
        int val;

        DequeNode(int val) {
            this.val = val;
        }

        DequeNode(int val, DequeNode prev, DequeNode next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
}

K Distinct Array CodeChef Solution in PYPY 3

import sys
#import random
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
#sys.setrecursionlimit(10**8)
from queue import PriorityQueue as pq
from math import gcd
#import math
input_ = lambda: sys.stdin.readline().strip("\r\n")
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab,bc,cd : ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x : print(x)
prinT = lambda x : print(x)
f = lambda : sys.stdout.flush()
inv =lambda x:pow(x,mod-2,mod)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
mod = 10**9 + 7
mod1 = 998244353

for _ in range (ii()) :
    n,k = il()

    ans = []

    for i in range (n,-1,-1) :
        if ( (i*(i+1))//2 + (n - i) <= k) :
            for j in range (i,0,-1) :
                ans.append(j)

            v = k - (i*(i+1))//2 - (n-i)

            while (len(ans) < n) :
                ans.append(v + 1)

            print(*ans)

            break

K Distinct Array CodeChef Solution in C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Chal_Feb22
{
    class Program
    {
        static void Main(string[] args)
        {
            int T;

            T = Int32.Parse(Console.ReadLine());

            // Random Rgen = new Random();

            for (; T > 0; T--)
            {
                int N; long K;

                var infromln = Console.ReadLine().Split(' ');

                N = Int32.Parse(infromln[0]);

                K = Int64.Parse(infromln[1]);

                var DIntsByPer = Enumerable.Range(0, N).Select(fn => (N - fn + N + 0L) * (fn + 1L) / 2).ToArray();

                int bs = Array.BinarySearch(DIntsByPer, K);
                bs = (bs >= 0) ? bs : (~bs - 1);
                long KPeriod = DIntsByPer[bs];

                long AddVals = K - KPeriod;

                int[] A = new int[N];

                for (int i = 0; i < N; i++)
                {
                    A[i] = ((i <= bs + AddVals) ? (i % (bs + 2) + 1) : A[i - bs - 1]);
                }

                
                Console.WriteLine(String.Join(" ", A));
            }

            Console.ReadLine();
        }
    }
}

K Distinct Array CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func main() {

	reader := bufio.NewReader(os.Stdin)

	tc := readNum(reader)
	var buf bytes.Buffer
	for tc > 0 {
		tc--
		var n int
		var k uint64
		s, _ := reader.ReadBytes('\n')
		pos := readInt(s, 0, &n)
		readUint64(s, pos+1, &k)
		res := solve(n, int64(k))
		for i := 0; i < len(res); i++ {
			buf.WriteString(fmt.Sprintf("%d ", res[i]))
		}
		buf.WriteByte('\n')
	}
	fmt.Print(buf.String())
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' {
			return s[:i]
		}
	}
	return s
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func solve(n int, k int64) []int {
	// [1...i] = (i * (i - 1) / 2) good
	arr := make([]int, n)
	k -= int64(n)

	var p int
	var cur int64

	for k >= cur {
		arr[p] = int(cur + 1)
		p++
		k -= cur
		cur++
	}

	for p < n {
		arr[p] = int(cur - k)
		p++
	}

	return arr
}
K Distinct Array CodeChef Solution Review:

In our experience, we suggest you solve this K Distinct Array CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the K Distinct Array CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this K Distinct Array CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *