1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
n200080 [17]
3 years ago
9

Given an array A of size N, and a number K. Task is to find out if it is possible to partition the array A into K contiguous sub

arrays such that the sum of elements within each of these subarrays is the same.Prerequisite : Count the number of ways to divide an array into three contiguous parts having equal sum
Computers and Technology
1 answer:
Dennis_Churaev [7]3 years ago
6 0

Answer: First lets solve the Prerequisite part

Lets say we have an input array of N numbers {3,2,5,0,5}. We have to  find number of ways to divide this array into 3 contiguous parts having equal sum. So the output for the above input array will be 2 as there are 2 ways to divide the array. One is (3,2),(5),(0,5) and the other is (3,2),(5,0),(5).

Following are the steps to achieve the above outcome.

  • Let p and q point to the index of array such that sum of array elements from 0 to p-1 is equal to sum of array elements from p to q which is equal to the sum of array elements from q+1 to N-1.  
  • If we see the array we can tell that the sum of 3 contiguous parts is 5. So the condition would be that sum of all array elements should be equal to 5 or sum of each contiguous part is equal to sum of all array elements divided by 5.
  • Now create 2 arrays prefix and postfix of size of input array. Index p of prefix array carries sum of input array elements from index 0 to index p. Index q of postfix array carries sum of input array elements from index p to index N-1
  • Next move through prefix array suppose at the index p of prefix array : value of prefix array == (sum of all input array elements)/5.
  • Search the postfix array for p index found above. Search it starting from p+2 index. Increment the count variable by 1 when the value of postfix array =(sum of all input array elements)/5 and push that index of postfix array into a new array. Use searching algorithm on new array to calculate number of values in postfix array.

Now lets solve the main task

We have an array A of size N and a number K. where A[]= {1,6,3,4,7} N=5 and K=3. We have to find if its possible to partition A into 3 contiguous subarrays such that sum of elements in each subarray is the same. It is possible in this example. Here we have 3 partitions (1,6),(3,4),(7) and sum of each of subarrays is same (1+6) (3+4) (7) which is 7.

Following are the steps to achieve the above outcome.

  • In order create K contiguous subarrays where each subarray has equal sum, first check the condition that sum of all elements in the given array should be divisible by K. Lets name another array as arrsum that will be the size of array A. Traverse A from first to  last index and keep adding current element of A with previous value in arrsum. Example A contains (1,6,3,4,7} and arrsum has {1,7,10,14,21}
  • If the above condition holds, now check the condition that each subarray or partition has equal sum. Suppose we represent sum1 to sum of all element in given array and sum2 of sum of each partition then: sum2 = sum2 / K.
  • Compare arrsum to subarray, begining from index 0 and when it becomes equal to sum2 this means that end of one subarray is reached. Lets say index q is pointing to that subarray.
  • Now from q+1 index find p index in which following condition holds: (arrsum[p] - arrsum[q])=sum2
  • Continue the above step untill K contigous subarrays are found. This loop will break if, at some index, sum2 of any subarray gets greater than required sum2 (as we know that every contiguous subarray should contain equal sum).

A easier function Partition for this task:

int Partition(int A[], int N, int k) // A arra y of size N and number k

{      int sum = 0;    int count = 0;  //variables initialization    

   for(int j = 0; j < N; j++)  //Loop that calculates sum of A

  sum = sum + A[j];        

  if(sum % k != 0) //checks condition that sum of all elements of A should be //divisible by k

   return 0;        

   sum = sum / k;  

   int sum2 = 0;  //represents sum of subarray

  for(int j = 0; j < N; j++) // Loop on subarrays

  {      sum2=sum2 + A[j];  

   if(sum2 == sum)    { //these lines locates subarrays and sum of elements //of subarrays should be equal

       sum2 = 0;  

       count++;  }  }  

/*calculate count of subarrays whose

sum is equal to (sum of complete array/ k.)

if count == k print Yes else print No*/

if(count == k)    

return 1;  

   else

   return 0;  }

You might be interested in
Match each method of communication with its intended purpose.
Scorpion4ik [409]

Answer:

1. a late breaking news story = to inform

2. a poetry reading = to entertain

3. an advertisement = to persuade

4. a small group assignment = to collaborate

Explanation:

1. A "breaking news" tells people of what is happening in the society. It <em>informs </em>them of the occurrence of an important event such as the plane crash of Kobe Bryant.

2. Poetry reading is meant to touch the attention of listeners. It tries to entertain them through the poem's interesting verses.

3. An advertisement is being shown/displayed in order to convince people to buy a particular product or service.

4. A group assignment allows the members of the group to contribute their ideas together. Such situation is known as "collaboration." They try to brainstorm together towards a common goal.

7 0
3 years ago
What is one way to maintain Internet safety? a) avoid interacting with people on the Internet. B) avoid giving out information a
Anarel [89]
To be safe on the Internet, we must avoid giving out personal information.
4 0
3 years ago
You are tasked with securing a small network for a client in which the following requirements must be met: If a user on the priv
mario62 [17]

Answer:

C

Explanation:

It is best to Implement a UTM appliance.

A Unified Threat Management (UTM) system is a type of network hardware appliance, virtual appliance or cloud service that protects businesses from security threats in a simplified way by combining and integrating multiple security services and features.

DescriptionUnified threat management is an approach to information security where a single hardware or software installation provides multiple security functions. This contrasts with the traditional method of having point solutions for each security function.

Cheers

8 0
3 years ago
Who would be a tippee for purposes of insider trading? a. a janitor who gathers information by reading files on corporate counse
vesna_86 [32]

Answer:

Option A is correct.

Explanation:

A janitor that collects data through reviewing reports on a business counsel's desk could be a tippee for insider trading activities.

Probably, the justification for insider trading remains wrong being that it offers each insider the undue benefit on and around the marketplace, gets the insider's preferences beyond them for which they assume the trustee responsibility, as well as enables the insider to unfairly manipulate the cost of the inventory of a business.

So, the following are the reason the other options are not correct according to the given scenario.

3 0
3 years ago
write a function that counts the number of times the value of y occurs in the first n values in array x. y is an integer variabl
mixer [17]

Answer:

Following are the function of count:

void count(int y,int x[],int n) // function definition of count

{

int k,count=0;  // variable declaration

for(k=0;k<n;++k) // iterating over the loop

   {

   if(x[k]==y) //check the conndition number of times the value of y occurs

   {

   count++; // increment of count by 1

   }

   }

Explanation:

Following are the code in c language

#include <stdio.h> // header file  

void count(int y,int x[],int n) // function definition of count

{

int k,count=0;  // variable declaration

for(k=0;k<n;++k) // iterating over the loop

   {

   if(x[k]==y) //check the conndition number of times the value of y occurs

   {

   count++; // increment of count by 1

   }

   }

   printf(" the number of times the value of y occurs :%d",count); // display count value

   }

int main() // main method

{

   int x[100],y,n,k; // variable declarartion

   printf(" Enter the number of terms n :");

   scanf("%d",&n); // input the terms

   printf(" Enter the array x :");

   for(k=0;k<n;++k) // input array x

   {

   scanf("%d",&x[k]);

   }

   printf("Enter the value of y:");

   scanf("%d",&y);// input value y by user

    count(y,x,n); // calling function

   return 0;

}

In the given program we declared an array x ,variable  y and n respectively Input the array x ,y,n  by user after that we call the function count .In the count function we iterate the loop from o position to array length-1 and check the number of times the value of y occurs by using if statement  i.e  if(x[k]==y) if the condition of if block is true then we increment the count variable Otherwise not .Finally display the count variable which describe the number of count.

Output

Enter the number of terms n :5

1

2

2

56

5

Enter the value of y:2

the number of times the value of y occurs :2

Enter the number of terms n :5

1

2

3

56

5

Enter the value of y:26

the number of times the value of y occurs :0

7 0
3 years ago
Other questions:
  • Why do we need the Domain Name System (DNS)? Given the domain name www.flamingflamingos.eu, what is the top level domain in this
    5·1 answer
  • Which BI tool or technique would be most useful in predicting the likelihood of a fire in a building? a. Data mining b. Dashboar
    9·1 answer
  • A ________ is a collection of forms, reports, queries, and programs that serves as an intermediary between users and database da
    6·1 answer
  • What’s bigger 4,000,000 KB or 2.8 GB
    5·2 answers
  • Which of these is one of the primary concerns for protecting your family when online?
    9·2 answers
  • What to do if your monitor is not displaying a picture
    12·1 answer
  • How do you access the <br><br>internet in your school and at home?​
    11·1 answer
  • I need it in code please (python)
    15·2 answers
  • Question 8 A data analyst is working with a data frame named stores. It has separate columns for city (city) and state (state).
    12·1 answer
  • Which version of java should i use?.
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!