Horje
Check if it is possible to construct an array with the given conditions

Given integers N and K and an array A[] of M integers. The task is to check if it is possible to construct an array of size N such that-

  •  All the K consecutive elements of the array are distinct.
  • Considering 1-based indexing, the integer i can be used A[i] times to construct the array.

Note that sum of all elements of array is A[] is guaranteed to be N.

Examples :

Input : N=12, M=6, K=2, A[]={2,2,2,2,2,2}
Output : YES
Explanation : Consider the array {1,2,1,2,3,4,3,4,5,6,5,6}. It can be seen that any 2 consecutive elements are different (as K=2). Also, as per the array A[], all the integers from 1 to 6 are used twice.

Input : N=12, M=6, K=2, A[]={1,1,1,1,1,7}
Output : NO

Approach :

Let num = N/K.

We divide the final array into contiguous subarrays of length num each, except the last subarray (which will have length say len = N%K).

Observation – 1:

Every element of given array A[] should be smaller than or equal to ceil(N/K).

This is because each A[i] has to be used A[i] times in construction of the resultant array. In case, any A[i] is greater than ceil(N/K), it has to be present twice in atleast one subarray of the resultant array to meet the required conditions.

Then, we will count the number of A[i] which are equal to ceil(N/K) (or basically num+1).  

Observation – 2 :

The count of such elements must be smaller than or equal to len (which is the length of last subarray).

Steps involved in the implementation of code:

  • For each element A[i] of A, follow the steps 4 and 5.
    • If A[i] is equal to num+1, increment count by 1.
    • Else if A[i] is greater than num+1, make flag equal to 0 as it won’t be possible to construct the array.
  • At the end of iteration, check if flag is 1 and count is less than or equal to len. If so, return 1, else return 0.

Below is the implementation of the above approach:

C++

// C++ code for the
//above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to check if it is
// possible to construct an array
// with the given conditions
bool isPossible(int N, int M, int K, int A[])
{
    // num stores the number
  //of partitions of size K
    // of the final array
    int num = N / K;
 
    // len stores the length of last
    // partition whose length
  //is less than K
    int len = N % K;
 
    // Count stores the Number of
    // elements of array A whose
    // value are equal to num+1
    int count = 0;
 
    // Flag variable to check if
    // there is a valid
  //answer or not
    int flag = 1;
 
    // Iterating through the given
    // array A
    for (int i = 0; i < M; i++) {
        if (A[i] > num) {
           
            // If ith element of A
            // is equal to num+1,
            // increment count
            if (A[i] == num + 1) {
                count++;
            }
 
            // else if ith element is greater
            // than num+1, make flag=0
            else {
                flag = 0;
            }
        }
    }
 
    if (flag) {
        // If flag = 1 and count is less
        // than or equal to len, return 1
        if (count <= len) {
            return 1;
        }
 
        // else return 0
        else {
            return 0;
        }
    }
 
    // If flag is 0, return 0
    else {
        return 0;
    }
}
 
// Driver code
int main()
{
    int N = 12, M = 6, K = 2;
    int A[] = { 2, 2, 2, 2, 2, 2 };
    int answer = isPossible(N, M, K, A);
    if (answer == 1) {
        cout << "YES" ;
    }
    else {
        cout << "NO";
    }
}

Java

import java.util.Arrays;
 
public class GFG {
     
    // function to check if it is possible to construct an array
    // with the given conditions
    public static boolean isPossible(int N, int M, int K, int[] A) {
        // num stores the number of partitions of size K
        // of the final array
        int num = N / K;
 
        // len stores the length of the last partition
        // whose length is less than K
        int len = N % K;
 
        // Count stores the number of elements of array A whose
        // value is equal to num+1
        int count = 0;
 
        // Flag variable to check if there is a valid answer or not
        boolean flag = true;
 
        // Iterating through the given array A
        for (int i = 0; i < M; i++) {
            if (A[i] > num) {
                // If the ith element of A is equal to num+1,
               // increment count
                if (A[i] == num + 1) {
                    count++;
                }
                // else if the ith element is greater than num+1,
               // make flag false
                else {
                    flag = false;
                }
            }
        }
 
        if (flag) {
            // If flag is true and count is less than or equal to len,
           // return true
            if (count <= len) {
                return true;
            }
            // else return false
            else {
                return false;
            }
        }
        // If flag is false, return false
        else {
            return false;
        }
    }
 
    // Driver code
    public static void main(String[] args) {
        int N = 12, M = 6, K = 2;
        int[] A = {2, 2, 2, 2, 2, 2};
        boolean answer = isPossible(N, M, K, A);
        if (answer) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

Python3

# Python code for the  above approach
 
# Function to check if it is
# possible to construct an array
# with the given conditions
def isPossible(N, M, K, A):
 
    # num stores the number
    # of partitions of size K
    # of the final array
    num = N // K
 
    # len stores the length of last
    # partition whose length
    # is less than K
    len = N % K
 
    # Count stores the Number of
    # elements of array A whose
    # value are equal to num+1
    count = 0
 
    # Flag variable to check if
    # there is a valid
    # answer or not
    flag = 1
 
    # Iterating through the given
    # array A
    for i in range(M):
        if A[i] > num:
 
            # If ith element of A
            # is equal to num+1,
            # increment count
            if A[i] == num + 1:
                count += 1
 
            # else if ith element is greater
            # than num+1, make flag=0
            else:
                flag = 0
 
    if flag:
 
        # If flag = 1 and count is less
        # than or equal to len, return 1
        if count <= len:
            return 1
 
        # else return 0
        else:
            return 0
 
    # If flag is 0, return 0
    else:
        return 0
 
 
# Driver code
N = 12
M = 6
K = 2
A = [2, 2, 2, 2, 2, 2]
answer = isPossible(N, M, K, A)
if answer == 1:
    print("YES")
else:
    print("NO")
 
# This code is contributed by Tapesh(tapeshdua420)

C#

// C# code for the above approach
 
using System;
 
public class GFG {
    // function to check if it is possible to construct an
    // array with the given conditions
    static bool isPossible(int N, int M, int K, int[] A)
    {
        // num stores the number of partitions of size K
        // of the final array
        int num = N / K;
 
        // len stores the length of the last partition
        // whose length is less than K
        int len = N % K;
 
        // Count stores the number of elements of array A
        // whose value is equal to num+1
        int count = 0;
 
        // Flag variable to check if there is a valid answer
        // or not
        bool flag = true;
 
        // Iterating through the given array A
        for (int i = 0; i < M; i++) {
            if (A[i] > num) {
                // If the ith element of A is equal to
                // num+1,
                // increment count
                if (A[i] == num + 1) {
                    count++;
                }
                // else if the ith element is greater than
                // num+1,
                // make flag false
                else {
                    flag = false;
                }
            }
        }
 
        if (flag) {
            // If flag is true and count is less than or
            // equal to len,
            // return true
            if (count <= len) {
                return true;
            }
            // else return false
            else {
                return false;
            }
        }
        // If flag is false, return false
        else {
            return false;
        }
    }
 
    // Driver code
    static void Main()
    {
        int N = 12, M = 6, K = 2;
        int[] A = { 2, 2, 2, 2, 2, 2 };
        bool answer = isPossible(N, M, K, A);
        if (answer) {
            Console.WriteLine("YES");
        }
        else {
            Console.WriteLine("NO");
        }
    }
}
 
// This code is contributed by ragul21

Javascript

// function to check if it is
// possible to construct an array
// with the given conditions
function isPossible(N, M, K, A) {
  
  // num stores the number
  //of partitions of size K
  // of the final array
  let num = Math.floor(N / K);
   
  // len stores the length of last
  // partition whose length
  //is less than K
  let len = N % K;
   
  // Count stores the Number of
  // elements of array A whose
  // value are equal to num+1
  let count = 0;
   
  // Flag variable to check if
  // there is a valid
  //answer or not
  let flag = 1;
   
  // Iterating through the given
  // array A
  for (let i = 0; i < M; i++) {
    if (A[i] > num) {
     
      // If ith element of A
      // is equal to num+1,
      // increment count
      if (A[i] === num + 1) {
        count++;
      }
      // else if ith element is greater
      // than num+1, make flag=0
      else {
        flag = 0;
      }
    }
  }
   
  if (flag) {
   
      // If flag = 1 and count is less
    // than or equal to len, return 1
    if (count <= len) {
      return 1;
    }
    // else return 0
    else {
      return 0;
    }
  }
  // If flag is 0, return 0
  else {
    return 0;
  }
}
 
 
// Test case
 
let N = 12, M = 6, K = 2;
let A = [2, 2, 2, 2, 2, 2];
let answer = isPossible(N, M, K, A);
 
if (answer === 1) {
  console.log("YES");
} else {
  console.log("NO");
}

Output

YES

Time Complexity : O(M)
Auxiliary Space : O(1)


 


Reffered: https://www.geeksforgeeks.org

Algorithms

Related
Introduction to Knapsack Problem, its Types and How to solve them Introduction to Knapsack Problem, its Types and How to solve them
10 Most Important Algorithms For Coding Interviews 10 Most Important Algorithms For Coding Interviews
Difference between Greedy Algorithm and Divide and Conquer Algorithm Difference between Greedy Algorithm and Divide and Conquer Algorithm
Transform and Conquer Technique Transform and Conquer Technique
Must Do Coding Questions for Product Based Companies Must Do Coding Questions for Product Based Companies

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje