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 list test_list = [ 4 , 7 , 10 , 13 , 16 , 19 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing K K = 3 res = True for idx in range ( len (test_list) - 1 ): # flagging if not found if test_list[idx + 1 ] ! = test_list[idx] + K: res = False # printing results print ( "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 list test_list = [ 4 , 7 , 10 , 13 , 16 , 19 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing K K = 3 # using all() to check for all elements res = all (test_list[idx + 1 ] = = test_list[idx] + K for idx in range ( len (test_list) - 1 )) # printing results print ( "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 list test_list = [ 4 , 7 , 10 , 13 , 16 , 19 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing K K = 3 res = False a = 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 results print ( "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 list test_list = [ 4 , 7 , 10 , 13 , 16 , 19 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing K K = 3 # using set() and all() function k_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 results print ( "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