Help to optimize code

general
1

cook your dish here

for _ in range(int(input())):
length = int(input())
nums = input().split()

try:
    index = nums.index('0')
except ValueError:
    index = length

count = 0
min_moves = float('inf')

while index != 0:
    non_zero_count = sum(1 for num in nums if num != '0')
    d = count + non_zero_count

    for i in range(index):
        num = int(nums[i])
        if num != 0:
            nums[i] = str(num - 1)

    count += 1

    min_moves = min(min_moves, d)

    try:
        index = nums.index('0')
    except ValueError:
        index = length

count += sum(1 for num in nums if num != '0')
min_moves = min(min_moves, count)

print(min_moves)

This is the solution which i was trying to Make All Zero Practice Coding Problem - CodeChef

Now why does it fail in time limit in the 4th test case, how can i optimise this without any logic changes?

2 
# cook your dish here
for _ in range(int(input())):
    length = int(input())
    nums = input().split()

    try:
        index = nums.index('0')
    except ValueError:
        index = length

    count = 0
    min_moves = float('inf')

    while index != 0:
        non_zero_count = sum(1 for num in nums if num != '0')
        d = count + non_zero_count

        for i in range(index):
            num = int(nums[i])
            if num != 0:
                nums[i] = str(num - 1)

        count += 1

        min_moves = min(min_moves, d)

        try:
            index = nums.index('0')
        except ValueError:
            index = length

    count += sum(1 for num in nums if num != '0')
    min_moves = min(min_moves, count)

    print(min_moves)

type or paste code here

3

@banibrata2007
u have to maintain hash for the prefix minimum and then calculate for each index.
plzz refer my c++ code for better understanding of the logic

#include <bits/stdc++.h>
using namespace std;
#define int long long int 
int32_t main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int a[n];
	    int ans=0,fans=n;
	    map<int,int> mp;
	    int mn=INT_MAX;
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	        mn=min(mn,a[i]);
	        mp[i]=mn;
	    }
	    int cmp=0,d;
	    for(int i=n-1;i>=0;i--)
	    {
	        if(mp[i]>cmp)
	        {
	            d=mp[i]-cmp;
	            cmp=mp[i];
	            ans+=d;
	            
	            if(a[i]>mp[i])
	            ans++;
	        }
	        else
	        {
	            if(a[i]>mp[i])
	            ans++;
	        }
	        fans=min(fans,ans+i);
	    }
	//    ans=min(ans,n);
	    cout<<fans<<endl;
	}

}
4

Thanks i got it, i was changing the list everytime by reducing each element before by 1 and that was causing lot of time usage
And you have already created another list to get the number to be reduced which saves a lot of time!

1 Like