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
Sally needs to copy data from the first worksheet to the fifth worksheet in her workbook. Which combination of keys will she use
Marta_Voda [28]

To make things faster, instead of using your mouse to navigate multiple Microsoft Excel sheets that are in the same document, you can use a shortcut instead. This is what Sally will be doing to copy data from her first worksheet to the fifth.

The shortcut function that Sally needs to use to achieve this is (A) Ctrl and Page Up or Page Down Keys.

7 0
3 years ago
Read 2 more answers
Does the security burden fall primarily on the user? On
liubo4ka [24]

Answer:

yes and no because of the security

Explanation:

yes and no because of the security

6 0
3 years ago
Who created the first photograph
Tems11 [23]
Nicephore Niepce created the first photograph.
8 0
3 years ago
Read 2 more answers
In which type of attack do you get malicious code in links from seemingly reliable websites?
natali 33 [55]

I think it is C. cross-site scripting

6 0
3 years ago
HELP PLZZ WILL MARK BRAINLIEST
adoni [48]

Answer:

if you could capture another image of this work bc I cant make out some words I can barley make out words

4 0
3 years ago
Other questions:
  • The ______ identifies the path for the currently open folder
    8·2 answers
  • Assuming that t is an array and tPtr is a pointer to that array, which expression refers to the address of element 3 of the arra
    7·1 answer
  • In JAVA,
    10·1 answer
  • The _____ handles the instructions for your computer to start up before the operating system is loaded.
    10·1 answer
  • Write a program to accept 10 different whole number from the user and store them in a
    11·1 answer
  • Erewrxdnnefwn q wedsvd
    6·1 answer
  • Deb needs to add borders on the cells and around the table she has inserted into her Word document.
    7·1 answer
  • Well the last week has been kind of terrible...
    9·2 answers
  • he degree of operating leverage is equal to: Group of answer choices FC / OCF. VC / OCF. 1 FC / OCF. 1 VC / OCF. 1 Picture FC /
    9·1 answer
  • How does a passive attack differ from an active attack?
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!