Hi All,
I am stuck with one problem statement.
"You are given an array. Now the task is to arrange array elements in such a way that sums of consecutive pair should not be divisible y 3. For example input array, to the function, is [1,2,6,3] then output array(solution) should be [1,6,2,3].
Explanation 1+2=3, so we replaced say 2 with 6. Now array will be [1,6,2,3].
Now 1+6=7; 6+2=8; 2+3=5. Since none of the sums of the pair is divisible by 3, we can return this modified array as the answer. I have solved this problem with a simple brute force approach, but looking better-optimized solution. Any help or suggestions are appreciated.
3 Likes
Can u tell me your brute Force…
First divide the array in groups a%3 = 0 array , a%3 = 1 array and a%3 = 2 array
now you will have 3 arrays
your goal is now make new array, by combing the arrays in such a way that,
if you take an element from modulus = 0 array, you shouldn’t add element from modulus = 0 array after that
and if you element from modulus = 1 array , you shouldn’t add element from modulus = 2 array or vice versa after that
I really want to know about the brute force method you used.
But let me give a simple solution for it.
Solution:
Take 2 empty arrays each of length (n//2)+1. Note: (n//2 gives the floor value of the quotient)
Now, use a for loop and iterate through every item in given array. If arr[i]%3==0 add them to 1st array, else add to 2nd array.
Now create another array by taking elements alternately from array 1 and 2.
Complexity:
By using this, the time complexity will be 2n and space complexity will be n. That’s the least possible complexity you can achieve for this question.
Note:
You’ll have one small problem here. One of the 2 array’s will have one element more than the other when main array has odd number elements. You’ll have to choose the largest array first while taking elements alternately.
I’ll leave that for you to figure out.
Please remember to send me your solution.
Thankyou.
1 Like
The approach I used was simple.
I iterated through the array i=0 to i< n-1
Inside loop check if arr[i] + arr[i+1] is divisible by 3 or not, if divisible by 3, then try replace by i+1 element from any element from right side loop k=i+2 to k<n. If we get such element whose sum with i is not divisible by 3 then swap element at index i+1 with element at index k it. If we don’t get such element on right side then iterate backwards from j= i-1 to j>=0. Try to find element which we can swap with i+1 element. Since here we are going to swap from left side we should also check swapping does not break existing logic(consecutive sum should not be divisible by 3) on left side. If we don’t get such element then print error msg and otherwise move ahead with i loop to check other elements.
What u written here… Tell me
you can use two for loops where one will move the array and other will swap the elements if their sum is divisible by 3.
where you can use a if statement to use the given condition.
1 Like