1658. Minimum Operations to Reduce X to Zero

 avatar
unknown
csharp
3 years ago
2.7 kB
11
Indexable
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;
    }
}