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
Anyone have any website ideas I could use for my computing website project? Thank you.
nlexa [21]
Yes like keynote yup keynote I use a lot of PowerPoints on keynote Yk
8 0
2 years ago
Read 2 more answers
How to play music out of your apple watch?
Travka [436]
It does not work that way....I thought the same thing. The sound will always come out of your iPhone
6 0
3 years ago
What are the design concepts and assumptions behind a class, an object and the relationship between them? What are the roles met
Triss [41]

Answer:

Object-oriented programming (OOP) is a procedural language and based on classes associated with an object. Without classes and object relationship OOP is not possible. According to program's design concept classes provide abstraction and encapsulation with the help of object. Object have states and behaviors like cat has states like name, color and  cat has also behaviors like  wagging the tail, eating, jumping etc. A class forms template or blueprints for these states and behaviors because different cats have different behaviors and states.

Methods provide a way for encapsulation and accessing private class members with public methods and static fields are sometimes best alternative for global variable. We can use static field when it same for all and shared by all objects of that class and it can save memory because we do not have to initialize it for each object

8 0
3 years ago
Definition of powerpoint animation
saul85 [17]

Answer:

An powerpoint animation is an animation that uses powerpoint or another similar app like google slides to create a video, game, or movie.

but...

If you mean just in Microsoft Office it's a visual or sound effect that you can add to slides to make them more interesting.

Explanation:

3 0
3 years ago
Many of today’s digital devices operate on battery power supplied by what kind of ion batteries.
stich3 [128]
"Lithium ion" is used in your cellphone.
6 0
3 years ago
Other questions:
  • How do type declaration statements for simple variables affect the readability of a language, considering that some languages do
    10·1 answer
  • True or false the primary advantage of the worksheet is the ability to solve numerical problems quickly and accurately
    11·1 answer
  • A new company is upgrading a media workstation. The computer will be predominantly used for graphic intensive presentations, sli
    13·1 answer
  • PLEASE HELP ME ON THIS..............PLEASEEEEEEEEEEEE PLEASEEEEEE<br><br> ITTS EASYYYYYYYY
    12·1 answer
  • Technology offers a variety of rich opportunities available to teachers and students. According to Inan and Lowther (2010), ther
    6·1 answer
  • PLEASE ANSWER ASAP
    7·1 answer
  • In general, the farther you are from other road users, the A. lower your crash risk B.higher your crash risk C. slower they are
    6·1 answer
  • How do you change the order of the slides in your presentation in the slide pane 
    15·2 answers
  • What is the advantage of entering metadata for electronic records that you create
    7·1 answer
  • What is the main advantage of using DHCP?
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!