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
Averigua las diferentes intensidades, la potencia total y el gasto en € (de un mes de 30 días con el equipo conectado todo el ti
Naily [24]

<u>Explanation</u>:

<u>Here's what the question entails in clearer detail;</u>

Find out the different intensities, the total power and the cost in € (from a 30-day month with the equipment connected all the time) in the following case: Component Voltage (V) Power (P) CPU 0.95 V 27.97 W RAM 1,257 V 2.96 W Graphics Card 3.28 V 75.3 W HDD 5.02 V 19.3 W Fans 12.02 V 2.48 W Motherboard 3.41 V 18.3 W

7 0
3 years ago
What is up with the bots? They are so annoying.
Yuki888 [10]

Answer:

very very very annoying

6 0
2 years ago
Read 2 more answers
Which is true regarding pseudocode?
drek231 [11]

Answer:

It uses simple words and symbols to communicate the design of a program.

Explanation:

4 0
3 years ago
Read 2 more answers
An organization is using Amazon CloudWatch Logs with agents deployed on its Linux Amazon EC2 instances.
Bumek [7]

Answer:

A and B

Explanation:

EC2 run command gives a management output to review various instances and servers. Here, the logging files, collecting metrics and patches, running script installations can be achieved.

Verify the user permission and the run command, confirms if whether or not the problem of missing logging files is from the settings.

There are several AWS and customer managed policies for cloudwatch logs to give users certain levels for permission. Verifying this determines if there is full access, group logs and creation of group log events, or even a read only access.

4 0
3 years ago
True / False<br> Generally, more orthogonal instruction sets are considered less elegant.
Cerrena [4.2K]

Answer: True

Explanation:Orthogonal instruction set is the set of instruction that can use can use all addressing mode. They have independent working and so instruction can use any register the prefer and this leads to overlapping in instruction and complexity.

When RISC architecture got introduced ,it got more preference due to reduced instruction and less complexity as compared to orthogonal instruction.So it not considered elegant to have more orthogonal instruction.

6 0
3 years ago
Other questions:
  • It is safe to use your bright headlights if there is a car ahead of you within 300 feet
    9·2 answers
  • Why was Unicode invented?
    6·1 answer
  • Select the correct answer.
    6·1 answer
  • Where do today's computers store almost all motherboard configuration data?
    15·1 answer
  • Multiple Choice
    6·1 answer
  • An index purports to speed data retrieval. you, therefore, index every attribute in each table. select the likely consequence.
    15·1 answer
  • why is the disk method a special case of the general slicing​ method? choose the correct answer below. a. the cross sections of
    7·1 answer
  • Which magazine introduced the first microcomputer kit for the mits altair in its january 1975 issue?
    8·1 answer
  • Random Access Memory is tempory computer memory that stores works in progress
    7·1 answer
  • What is the benefit of making an archive folder visible in the Outlook folder list?
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!