Given a List, check if the next element is always x + K than current(x).
Input : test_list = [3, 7, 11, 15, 19, 23], K = 4
Output : True
Explanation : Subsequent element difference is 4.Input : test_list = [3, 7, 11, 12, 19, 23], K = 4
Output : False
Explanation : 12 – 11 = 1, which is not 4, hence False
Method #1 : Using loop
In this, we iterate for each element of list, and check if the element is not K increasing if found, the result is flagged false and returned.
Python3
# Python3 code to demonstrate working of# Check if List is K increasing# Using loop# initializing listtest_list = [4, 7, 10, 13, 16, 19]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 3res = Truefor idx in range(len(test_list) - 1): # flagging if not found if test_list[idx + 1] != test_list[idx] + K: res = False# printing resultsprint("Is list K increasing ? : " + str(res)) |
The original list is : [4, 7, 10, 13, 16, 19] Is list K increasing ? : True
Time complexity: O(n)
Auxiliary Space: O(1)
Method #2 : Using all() + generator expression
In this, we check for all the elements being K increasing using all(), and generator expression is used for iteration.
Python3
# Python3 code to demonstrate working of # Check if List is K increasing# Using all() + generator expression# initializing listtest_list = [4, 7, 10, 13, 16, 19]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 3# using all() to check for all elementsres = all(test_list[idx + 1] == test_list[idx] + K for idx in range(len(test_list) - 1)) # printing resultsprint("Is list K increasing ? : " + str(res)) |
The original list is : [4, 7, 10, 13, 16, 19] Is list K increasing ? : True
Time Complexity: O(n)
Auxiliary Space: O(1)
Method #3 : Using min(),max() and for loop
Python3
# Python3 code to demonstrate working of# Check if List is K increasing# Using loop# initializing listtest_list = [4, 7, 10, 13, 16, 19]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 3res = Falsea=min(test_list)b=max(test_list)x=[]for i in range(a,b+1,K): x.append(i)if(x==test_list): res=True# printing resultsprint("Is list K increasing ? : " + str(res)) |
The original list is : [4, 7, 10, 13, 16, 19] Is list K increasing ? : True
Time complexity: O(n), where n is the number of elements in the list.
Auxiliary space: O(K), where K is the value of the increment between consecutive elements.
Method #4: Using set() and all() function
Algorithm:
- Initialize an empty set, k_set.
- Iterate over each element of the list, lst:
a. Check if the difference between the current element and the minimum element of the set is a multiple of K or not.
b. If it is not a multiple of K, return False.
c. If it is a multiple of K, add the current element to the set. - If all elements of the list pass the above condition, return True.
Python3
# Python3 code to demonstrate working of# Check if List is K increasing# Using set() and all() function# initializing listtest_list = [4, 7, 10, 13, 16, 19]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 3# using set() and all() functionk_set = set()res = all((not k_set) or ((x - min(k_set)) % K == 0 and k_set.add(x)) for x in test_list)# printing resultsprint("Is list K increasing ? : " + str(res)) |
The original list is : [4, 7, 10, 13, 16, 19] Is list K increasing ? : True
Time Complexity: O(n) where n is the length of the list.
Auxiliary Space: O(k) where k is the number of elements in the set
