1658. Minimum Operations to Reduce X to Zero
unknown
csharp
a year ago
2.7 kB
9
Indexable
Never
using System.Text.Json; public class Solution { public void Print(dynamic obj) { Console.WriteLine(JsonSerializer.Serialize(obj)); } public int MinOperations(int[] nums, int x) { List<int> leftSum = nums.ToList(); List<int> rightSum = nums.ToList(); Dictionary<int,int> leftDict = new(); Dictionary<int,int> rightDict = new(); int sum = 0; for(int i=0;i < nums.Length; i++) { sum += nums[i]; leftSum[i]=sum; leftDict[sum] = i; } if(x>sum) return -1; sum = 0; for(int i = nums.Length - 1; i >= 0; i--) { sum += nums[i]; rightSum[i] = sum; rightDict[sum] = i; } //Console.WriteLine(rightSum.Count); int minimumOps = Int32.MaxValue; //this.Print(leftSum); //this.Print(rightSum); //this.Print(leftDict); //this.Print(rightDict); int halfVal = nums.Length/2; //1,1,4,2,3 //1,2,6,8,11 //11,10,9,5,3 for(int i = 0; i < nums.Length; i++) { int target1 = x - leftSum[i]; int target2 = x - rightSum[nums.Length-1-i]; if(target1 == 0) { //Console.WriteLine($"i is {i} hitting target1 0"); minimumOps = Math.Min(minimumOps,i+1); } else if(rightDict.ContainsKey(target1)) { int targetPos = rightDict[target1]; int totOps = i+1+nums.Length-targetPos; if(i<targetPos) minimumOps = Math.Min(minimumOps,totOps); //Console.WriteLine($"i is {i} left target {target1} targetPos {targetPos} totOps {totOps} minimumOps {minimumOps}"); } if(target2 == 0) { //Console.WriteLine($"i is {i} hitting target2 0"); minimumOps = Math.Min(minimumOps,i+1); } else if(leftDict.ContainsKey(target2)) { int targetPos = leftDict[target2]; int totOps = i+1+targetPos+1; if(targetPos < nums.Length-i) minimumOps = Math.Min(minimumOps,totOps); //Console.WriteLine($"i is {i} right target {target2} targetPos {targetPos} totOps {totOps} minimumOps {minimumOps}"); } } return minimumOps == Int32.MaxValue ? -1 : minimumOps; } }